Открыть список
Как стать автором
Обновить
20
Карма
0.3
Рейтинг

Программист. Проект: сложный бот для игры КР2.

Проверка изоморфности двух графов и поиск изоморфных подграфов: подход на основе анализа NB-Paths

Очень жаль!
Получается, что фактически Вы описали эвристический алгоритм, но не приводя сам алгоритм — он только, м.б., у Вас в голове. Непонятно, чем Ваш подход лучше знаменитого инструмента NAUTY, который сделал Brendan D. McKay? Напомню, что я обсуждаю только первую часть Вашей статьи — изоморфизм графов. При таком подходе этот подход останется на уровне препринтов, т.е. его никто из спецов не заметит и не оценит.

Проверка изоморфности двух графов и поиск изоморфных подграфов: подход на основе анализа NB-Paths

При текущей реализации работает очень долго для графов с простой структурой
Понятно, что если сложность 17я степень от числа вершин, то на практике будет долго. Но важно доказать, что сложность — полином хоть 217 степени.

Проверка изоморфности двух графов и поиск изоморфных подграфов: подход на основе анализа NB-Paths

PS В препринте оговорка:
Применение данного подхода для поиска подграфов графа A, изоморфных
некоторому графу B, сможет находить лишь «вписанные» подграфы.

Означает ли это, что не всякий изоморфизм будет найден?

Проверка изоморфности двух графов и поиск изоморфных подграфов: подход на основе анализа NB-Paths

Спасибо!

Работаю над хим. приложениями графов (и не только химическим) не один десяток лет — про представления графов писал здесь на Хабре ранее. В статье предложено еще одно возможное представление — «NB-Paths». Ok.
У статьи две части: 1) задача изоморфизма и 2) поиск подграфов. Я буду говорить только об (1), т.к. пока (1) не доказана, про (2) говорить преждевременно.

М.б. мне показалось, что автор сделал аккуратный намек на решение задачи изоморфизма за полиномиальное время от числа вершин? — Возникает такое впечатление. Но где строгие определения, теоремы и доказательства? — Я не про данную статью — на Хабре допустим популярный стиль, я про препринт, упомянутый в статье. Интересно, что в статье сказано:
NB-путями (и не из англомании, а просто потому, что так – короче) мы будем называть maximal non-branching paths, т.е. максимально протяженные неразветвляющиеся пути некоторого графа.

А в препринте:
Последовательности максимально протяженных неразветвляющихся путей(maximal non-branching paths)
Ну так зачем наводить тень на плетень. Напишите в препринте:
Определение. NB-путями (maximal non-branching paths) мы будем называть последовательности максимально протяженных неразветвляющихся путей.
Далее:
Теорема (или Лемма). Если два графа изоморфны друг другу, то для любого
представления первого графа в виде NB-путей всегда существует соответствующее ему такое же представление второго графа.

Доказательство. [...] Что и требовалось доказать.
Далее нужно привести алгоритм поиска NB-путей в графе на псевдокоде. Читатель может не знать языка Х, который в реализации, и не должен разбираться с полным текстом программы. Оценку теоретического времени исполнения по псевдокоду вести легче. Приведите эту оценку для наихудшего случая. На этом ИМХО можно закончить. Но в сетке есть прекрасные БД «патологических графов», забраковавших многие предложенные решения задачи изоморфизма. Я постараюсь найти в своих архивах ссылки.
Если данный алгоритм справится с этими БД — это будет явным достижением, которое нужно отметить. Думаю, что препринт нужно направить в arXiv.org.
Сказанное выше не мои придирки, а многолетние впечатления от изданий типа J of Graph Theory.

Снупп Догг и «Голодные игры»: кто спасает книжную индустрию в период пандемии

Интересная статья. Спасибо.
На фотографиях книги в жестких переплетах. С большим количеством цветных картинок. Такие книги не удобно читать в электронной версии.
А как изменилась доля дешевых карманных книг в мягкой обложке, на дешевой бумаге, где только текст? И как меняется спрос на «читалки» для электронных книг?

Почему нам не нужно бессмертие

Чем больше будет вечных, тем меньше будет молодых…
Пока можем видеть, что дело в научных школах, где у молодых обычно роль исполнителей.
Не будет тех, кто подвергнет сомнениям основы.
Сейчас не только (и не сколько) молодые подвергают сомнениям основы. В альтернативной науке очень много немолодых.
А если будет меньше первокурсников, опровергающих Эйнштейна (см. выше), то ИМХО нука не пострадает. Более того сейчас большинство молодых хочет быстрее сделать карьеру. Поэтому они конформисты и слушают своего научного руководителя, чтобы быстрее защитить диссер. Может, если у молодого будет несколько сотен лет впереди, то он не будет соглашателем?

Почему нам не нужно бессмертие

В истории полно примеров, когда слишком революционные концепции были отвергнуты наглухо и к ним вернулись только спустя много лет — в том числе и после смерти как авторов, так и их критиков.
Но вернулись не ко всем, а только к некоторым — немногим от общего числа.
Если решения будут принимать бессмертные светила
Уже сейчас, если светило за 5 лет не написало не только книгу, но, даже, статью, его могут попросить в НИИ освободить занимаемое место, а в научном сообществе его рейтинг упадет до плинтуса.
Причем заметьте: черт его знает, насколько они успевают за наукой, но в риторике, и где-то даже в демагогии — им равных нет!
Риторикой и демагогией научного открытия не сделать. Наука не столь беззащитна, как может показаться со стороны. За многие годы наука накопила большой опыт противодействия. Другое дело, что в некоторые исторические периоды приходилось следовать линии партии, но это кончалось гораздо быстрее, чем 1000 лет. :)

Почему нам не нужно бессмертие

Сужение сферы интересов дает эффективность.

Которая нужна, чтобы всё-таки “добраться” лет за 30-40 до чего-то, что будет интересно не только лично ему, но и кому-то ещё.

30-40 лет обычно слишком много. Знаю многих научных работников, сделавших интересные работы в студенческие годы, и аспирантами сделали еще больше. Но кому-то и 40 лет мало.
Так вот до 3-5 лет детёнышы шимпанзе смышленее, чем дети! Говорить только не умеют, строение гортани не позволяет.
См. Обучение обезьян речи

Почему нам не нужно бессмертие

Однако то, что человек уже усвоил ранее — крайне редко подвергается сомнению.
Дело не в сомнении. Дело в способности забывать детали, при этом остается знание базовых принципов. Нпр., предположу, что почти все, окончившие ср. школу, помнят теорему Пифагора, хотя бы в формулировке «Пифагоровы штаны...» При этом далеко не все смогут ее доказать, хотя в школе учили доказательство к выпускному экзамену. Т.о. часть ОЗУ, занятое под детали, освобождается.
Утрируя: если вы уже на малых циклах — в общей химии вы революций не только не свершите, но и скорее всего — не допустите!
Придется допустить по обстоятельствам:
1) общей химией (ОХ) давно не интересуюсь настолько, чтобы читать все новости;
2) поэтому (1) узнаю о революции самым последним, когда она уже свершилась;
3) в ОХ я никто, поэтому мои возражения не будут слушать;
4) доказать ничего не смогу, т.к. много забыл;
5) вообще мне это не интересно — лучше продолжу изучать малые циклы;
6) пусть спецы в ОХ расхлебывают эту «кашу».

ИМХО Вы делаете ошибку слишком веря в романтический образ ученого-революционера, созданный околонаучной худ.лит. Посмотрите форумы физмат вузов: года не проходит, чтобы пара первокурсников не пыталась опровергнуть Эйнштейна и доказать необходимость деления на ноль. Но науке приходится быть консервативной, иначе ее сметут. Сметут не только революционеры, но и всякие Выбегалло (которых больше).

Почему нам не нужно бессмертие

Много нюансов.
Один из них: в жизни человек периодически специализируется. Нпр., начинал с общей химии, потом увлекся органикой, потом малыми циклами. Сужение сферы интересов дает эффективность.

Чему равно выражение -3/3u*3 на С++? Не угадаете. Ответ: -4. Приглашаю на небольшое расследование

Как справедливо отмечено в статье:
Боингов еще много летает.
Тоскливо…

Чему равно выражение -3/3u*3 на С++? Не угадаете. Ответ: -4. Приглашаю на небольшое расследование

ИМХО хорошие компиляторы должны быть совместимы с своими предыдущими версиями. Конечно, не всякий начальник одобрит переход на новый компилятор только для фиксации багов типизации. Но очень вероятно, что новый компилятор выдаст более оптимальный код и сам будет работать быстрее, а это уже серьезный довод для начальника. Затраты на переход со вставкой директив будут значительно меньше, чем написать весь код занаво.

Почему нам не нужно бессмертие

Появляются альтернативные науки ;)

Почему нам не нужно бессмертие

Представьте себе: Вы такой молодой, спортивный, 20-летний, выходите на ринг, а против вас выходит такой-же молодой, спортивный чувак, который последние 350 лет занимался боксом, профессионально, рефлексы которого отточены в миллионах боев, который за счет опыта может предугадать ваши действия.

ИМХО. Не проблема. Даже сейчас в спортивных соревнованиях есть возрастное деление. Есть детские соревнования, юниоров, взрослых. 10-летний мальчишка не сможет выступить против 30-летнего спортсмена. Ему не позволят. Тогда возрастных групп будет больше: от 20 до 80, от 81 до 140 и т.д.

Почему нам не нужно бессмертие

Если всё хранить в ОЗУ, то «емкости не хватит». Но что-то можно записать (на внешний носитель) и забыть. При этом нужно учитывать важное свойство информации — она сжимаема.

Почему нам не нужно бессмертие

С возрастом у многих происходит сдвиг в воспоминания, в историю своей проф. области (наука, техника, архитектура, музыка и т.д.) Но это полезно для всего человечества — посмотреть на пройденный вековой путь глазами очевидца.

Почему нам не нужно бессмертие

Способность к обучению и даже восприятию нового падает.

У меня другие наблюдения. Моя мама была историком и искусствоведом. В 80 лет она захотела научиться работать на ПК. В основном, чтобы статьи писать. Отдал ей старый Макинтош, потом более новый ПК. Она быстро осваивала при том, что на пишущей машинке никогда не печатала. Очень пожилые родители моих знакомых легко пользуются мобильной связью и Инетом. Привыкшие к наличным деньгам и к телевизорам 1960х, они запросто привыкают к банковским картам и к современным ТВ с ПДУ.

Чему равно выражение -3/3u*3 на С++? Не угадаете. Ответ: -4. Приглашаю на небольшое расследование

Согласен, что «Возможность выбора — это прекрасно»! Однако у тех, кто нанят поддерживать старый софт, нет выбора. ИМХО надежная типизация должна стать международным стандартом.

Чему равно выражение -3/3u*3 на С++? Не угадаете. Ответ: -4. Приглашаю на небольшое расследование

Спасибо за прекрасный пример проблемы возможности слабой типизации. Эту возможность зачастую выдают за достоинство ЯП: гибкость. И Википедия отмечает:
Сильная, но не полиморфная система типов может затруднить решение многих алгоритмических задач, как это было отмечено в отношении языка Pascal

Про Паскаль сказано:
Вариантная запись позволяет рассматривать тип данных различным образом в зависимости от указанного варианта.


Да, такой обход был в листингах из "developer documentation manuals Inside Macintosh". Ну так это в явном виде обход сильной типизации с добавлением нескольких строк кода. И только в нескольких редких случаях. Поэтому возражения сторонников слабой типизации не убеждают:

Так же найдутся, кто возразит, что ничего нельзя менять, поздно уже, много кода написано, и если в нём есть костыли, то он рухнет. Новые ошибки, они потом будут, а старые — они святое и уже превратились в знакомые фичи.

Как хорошую подсказку познавательно добавить предупреждение в компилятор когда он применяет это правило из Стандарта: «Signed value is intentionally converted to unsigned value. Sorry for crashing one more airplane. Have a nice flight!» Вот удивимся тогда, как мало мы тестируем и как много нам открытий чудных приносит компилятор друг.


Слабая типизация не должна быть по умолчанию. Сделайте директиву, отключающую типизацию, где это необходимо, а потом включающую. И старый код, после простой доработки, будет совместим с новым стандартом. При этом м.б. найдны баги, и спасено несколько Боингов.

Информация

В рейтинге
1,592-й
Зарегистрирован
Активность