Комментарии 17
Не вижу нигде упоминания алгоритма А* ( https://ru.wikipedia.org/wiki/Алгоритм_поиска_A* ) или хотя бы обычного поиска в ширину ( https://ru.wikipedia.org/wiki/Поиск_в_ширину ).
Что, подход «сперва учись, потом думай, потом делай» уже не в моде?
Посмотрите на картинки вот тут: http://buildnewgames.com/astar/, должно помочь!
Что, подход «сперва учись, потом думай, потом делай» уже не в моде?
Посмотрите на картинки вот тут: http://buildnewgames.com/astar/, должно помочь!
+12
Мне кажется, что не хуже и другой подход: «сперва думай, потом делай, затем учись, потом снова думай, и, наконец, делай превосходно». Пытаться реализовать что-то самому, не изучая детально готовые решения — очень полезно, на мой взгляд.
UPD: Однако, за ссылки спасибо.
UPD: Однако, за ссылки спасибо.
+5
A* бы тут плохо сработал, кстати, потому что эвристика на такой задаче может в тупик завести очень легко.
0
Навскидку: каждому существительному из словаря сопоставляем id.
Делаем карту переходов, возможных между id.
Таким образом отбрасываем необходимость работы со строками, остаемся наедине с цифрами, задача переводится немного в другую плоскость.
Дальше напрашивается построение графа и поиск пути между вершинами, ну или деревья. Я думаю с числовыми значениями алгоритм проще будет найти.
Делаем карту переходов, возможных между id.
Таким образом отбрасываем необходимость работы со строками, остаемся наедине с цифрами, задача переводится немного в другую плоскость.
Дальше напрашивается построение графа и поиск пути между вершинами, ну или деревья. Я думаю с числовыми значениями алгоритм проще будет найти.
+2
Хм. В третьей версии фактически так и есть.
Карта переходов — один из индексов в базе в таблице псевдослов — UNIQUE KEY `value_word_id` (`deleted_symbol_pos`,`value`,`word_id`). Его использование — в селекте MySQL маппера, вытаскивающего мутации из базы.
Попутно исключаются мутации «не в той позиции» и ид-шники уже имеющихся слов в цепочке.
Можно ли без значений псевдослов обойтись, типа «муа» и «тракан»? Можно. С другой стороны в базе всё равно поиск по индексу идёт, те же цифры в указателях влево-вправо в BTREE. Есть над чем подумать, спасибо.
Что касается дерева, или графа — по сути они ничего не меняют, это лишь разные представления одних и тех же метаграммных связей между словами, в данном случае выраженных индексом в таблице, самому являющемся по сути не совсем явно выраженным, но графом между метаграммными словами. И да, связи можно выразить легче, уже разобрался.
Карта переходов — один из индексов в базе в таблице псевдослов — UNIQUE KEY `value_word_id` (`deleted_symbol_pos`,`value`,`word_id`). Его использование — в селекте MySQL маппера, вытаскивающего мутации из базы.
кусок кода сборки запроса
// Выбираем все подходящие псевдослова из базы
$query = "SELECT wp.`word_id`, wp.`deleted_symbol_pos`, wp.`id`, wp.`value`, w.`value` AS `word`"
. " FROM `word_pseudo` AS wp"
. " JOIN `word` AS w ON (w.`id` = wp.`word_id`)"
. " WHERE w.`dictionary_id` = " . $this->_db->QuoteValue($this->_dictionary['id'])
. " AND w.length = " . $this->_db->QuoteValue($wordLen)
. " AND wp.`deleted_symbol_pos` = " . $this->_db->QuoteValue($mutPos)
. " AND wp.`value` = " . $this->_db->QuoteValue($pseudoWord)
. (
empty($excludedWordKeys) ? "" :
" AND wp.`word_id` NOT IN ("
. implode(',', array_map(function($key) {
return $this->_db->QuoteValue($key);
}, $excludedWordKeys))
. ")"
)
. " ORDER BY wp.`word_id`"
;
Попутно исключаются мутации «не в той позиции» и ид-шники уже имеющихся слов в цепочке.
Можно ли без значений псевдослов обойтись, типа «муа» и «тракан»? Можно. С другой стороны в базе всё равно поиск по индексу идёт, те же цифры в указателях влево-вправо в BTREE. Есть над чем подумать, спасибо.
Что касается дерева, или графа — по сути они ничего не меняют, это лишь разные представления одних и тех же метаграммных связей между словами, в данном случае выраженных индексом в таблице, самому являющемся по сути не совсем явно выраженным, но графом между метаграммными словами. И да, связи можно выразить легче, уже разобрался.
0
Ну да, очередной пример полезности теории графов. Эта задача сводится к поиску кратчайшего пути в графе. Если хранить граф в матричном виде, то получаем для 10к слов 10к * 10к бит = 12 мегабайт. С учетом неориентированности графа, память можно уполовинить до 6 мегабайт.
+5
Да, спасибо, то был ложный испуг масштабов вот тут:
Моя ошибка.
Ведь мы будем строить дерево из уникальных элементов (слов), а словарь-то не такой огромный, совсем не 10 млн слов, а на порядки меньше. А точнее, в нашем случае, 64765 слов.
Причём, распределение по длинам следующее:
С учётом того, что слова разной длины в «из мухи слона» друг с другом не связаны, минимальную оценку на данные графа по памяти можно дать как сумму полуквадратов по каждой из длин слов.
При этом каждый раз использовать для работы потребуется лишь одну из матриц, соответствующую рассматриваемым длинам слов.
Конкретно для 4-буквенных выйдет 3477 * (3477 — 1) / 2 бит = 740 Кб.
Совсем не страшно. Даже если хранить связь между словами не битом, а байтом, выйдет всего 6 Мб.
В байте связи кстати можно хранить не обязательно простой буль — может удобно выйдет хранит номер буквы, на которую различаются два связанных слова.
Определённо стоит переделать через дерево/граф.
Даже если дать очень оптимистичную оценку на среднее число вариантов модификаций в 5 (всего!), то если к какому-то слову минимальный путь составит 10 шагов, то в памяти должно уместиться дерево в 510 ~= 10 млн нодов
Моя ошибка.
Ведь мы будем строить дерево из уникальных элементов (слов), а словарь-то не такой огромный, совсем не 10 млн слов, а на порядки меньше. А точнее, в нашем случае, 64765 слов.
Причём, распределение по длинам следующее:
распределение
COUNT(*) length
111 2
956 3
3477 4
7224 5
8517 6
9356 7
8328 8
7540 9
5290 10
4315 11
2835 12
2346 13
1680 14
971 15
691 16
361 17
228 18
117 19
58 20
25 21
14 22
3 23
1 24
С учётом того, что слова разной длины в «из мухи слона» друг с другом не связаны, минимальную оценку на данные графа по памяти можно дать как сумму полуквадратов по каждой из длин слов.
При этом каждый раз использовать для работы потребуется лишь одну из матриц, соответствующую рассматриваемым длинам слов.
Конкретно для 4-буквенных выйдет 3477 * (3477 — 1) / 2 бит = 740 Кб.
Совсем не страшно. Даже если хранить связь между словами не битом, а байтом, выйдет всего 6 Мб.
В байте связи кстати можно хранить не обязательно простой буль — может удобно выйдет хранит номер буквы, на которую различаются два связанных слова.
Определённо стоит переделать через дерево/граф.
+3
Лина? Линн? Сион?
Ты вместо словаря существительных словарь имён собственных что ли раскурил?
Ты вместо словаря существительных словарь имён собственных что ли раскурил?
+2
Выше я оставлял ссылку, откуда втянул в словарь дополнительные слова — из одного из словарей кроссвордистов. А у кроссвордистов география и имена в ходу. Да, хорошо бы без них, но пока лучших словарей не обнаружил. Во всяком случае, в этих хоть нет глаголов, прилагательных и подобного.
Замечание уместное.
Разве что Сион — это ещё и «Вид православной церковной утвари, хранилище просфор (освященного хлеба)», а Линн — «Замок в Эстонии».
Замечание уместное.
Разве что Сион — это ещё и «Вид православной церковной утвари, хранилище просфор (освященного хлеба)», а Линн — «Замок в Эстонии».
0
Генетический алгоритм?? Зачем так сложно?? Ээээ, это задача WordLadder на leetcode со средней сложностью, обычный обход дерева в ширину! Причем решение мегаэлегантное, даже граф строить не надо, для коротких слов можно последовательно менять каждую букву и проверять на наличие в словаре — таким образом получим «ребро», которое кладем в очередь.
+5
Я тут быстренько попробовал на первом попавшемся словаре и из мухи в слона обычным BFS прихожу за 25 миллисекунд. Словарь далеко не 6 мегабайт, но этот поиск наверное займет резонное время и место даже на большом словаре.
муха-мура-мара-кара-каре-кафе-кафр-каир-каин-клин-клон-слон
long start = System.currentTimeMillis();
String[] dict = "кафр урюк быть весь этот мочь один себя свое если рука даже свой дело есть глаз день надо идти друг тоже лицо ведь жить нога пока хотя сила вода куда стол ночь отец дать твой лишь свет жена окно мать утро душа таки чуть хоть уйти пять путь пора тело язык мама небо брат туда мало труд сюда чтоб тихо двор иной угол губа снег либо дядя мера край река рота речь гора едва море врач ясно боль вещь цель план пара след пить мимо враг удар мало вниз двое счет игра член хлеб банк идея союз метр вера бить звук роль петь поэт лист выше этаж дочь опыт рост кожа баба дама поле ящик цена зато тень лето воля цвет круг факт стул вино ради танк зима знак семь мозг рыба щека папа срок курс куст явно чудо тема крик ключ конь штаб пора трое ужас ссср очко пыль боец черт царь даль слух клуб беда обед тетя лечь смех злой мост пуля мясо долг рада пиво зона вход итак пост дача рано ниже кино горе вряд суть стен толк вкус полк кофе база урок труп муха лапа плащ нету шкаф сеть грех парк борт луна волк пила файл куча пояс гриб слой изба юный пища храм рана холм доля воин тьма итог боже гном цепь ужин баня жест щель узел гроб шанс порт июнь март перо яйцо туча верх нерв этап заяц дума роза кадр июль фонд ныне виза груз ярко внук стук печь мина хрен соль руль мука штат течь блок дура каша кафе лифт трус мода сено поза брак плод окоп сидя вина сбор флот мыло стоя гнев плюс змея один уход звон нквд пляж слон дыра бред риск взор лужа орел нары юбка рожа дата стыд ноль юмор учет вица флаг грек марш вена диск теща алый удав сего лыжа плач цирк бюро село мышь шуба роса упор рама указ кран хата поди сухо нуль дуть очаг шлем буря мрак матч коза темп гром холл веко тьфу стон сорт заря сейф визг млрд семя осел пруд офис гусь доза стоп елка змей тоня орех туго пена живо кпсс сало коса толь мыть ранг негр ритм стая блин азия тигр икра худо овца фара вяло плот клок купе сани кура даба чушь овощ цикл язва ныть лорд плат нить чаша эфир мощь уста секс скот винт жечь яхта литр роща крым нота лихо жанр лежа лить леди киев шрам вред нева ниша нрав миля яков трон лень зять выть игла дина троп дитя пень дико шнур кора уток штык укол прут мент тост джип крюк бокс толя прах лось свод фига клещ мазь ядро корм русь залп клей клад жара иуда граф сука бинт хаос плен тупо мгла жопа грош батя эльф няня кода такт ваза чара урал фаза дуга мочь пуща ложе этак пина безо дева псих фунт дуло клан паук трап рыло град нора ожог спор рака вить джин жать шить араб липа тасс гага рыть тяга близ чадо клоп арка чаек обои клык нато фото клюв бунт трос отек сема меню вата жила мисс кара урод эдак ляля крем утюг мило рига езда усик узор кнут босс приз медь тушь перс моча марс косо пакт сень мари орда веня борщ алло шелк чаща веер раса шарф враз торт кайф моща тура выпь уйма ноша гарь пики лада маяк долл стих карп майя вонь крах серо лига зубр плац урна нива горб зола взад иней мсье депо хрип бомж шина дурь руда джаз герб мара дорн соус кедр пузо хвоя рейд сеул стаж жаба морг урка клин опор шест заем сени кабы харя йога трюм чека саше ушко гимн ямка хлам стан дань ладо вилы трюк зной паек блик рема слог тина квас жгут муть шаль пред сайт пята дьяк клен сечь швед лунь лязг гувд обоз вмиг пони балл щука степ жало корж укор ввод дичь утес скат воск сера щелк гиря жрец сова ежик шейк гута ирак юнец раба огпу бюст шило филя бора кейс серп пани вбок писк укус дыня вишь срыв идол лира пари сыпь нона ряса гной экий харч овес лиса фрак ушиб крот мура фрау мэтр лавр стог шифр гипс оный подо баян краб оспа муза цент бишь зуда наст убор кипр кпрф рута сушь жлоб зонт тест сажа гриф бант сбой авто итар атом гуща храп амур деть байт моль эсер чума загс дыба лава спец ковш торг улей сода рейх иран падь лоно раис мэри бусы кило чело жижа фойе киль рысь ново герр омут сбыт бита лата факс омон ария мена жуть ларь стык грач дуэт ярус вдох сыро срез плуг вьюк сноп пуск люкс соло шурф тайм тара удел буги агат спой флер сруб явка цинк ринг мель омар ясли срам сити круп фуга спид умно кров печь уезд спад паче марь горн этюд гнет роба ярый глум тишь улов куда жюри брод боек софа мять кндр ялта лупа елей чили плюс юрта зонд репа прок чета хост трлн грим брус ирма фила плед сито арап кипа пирс треп кума цска стер тент лыко гать лоза путч доха куль жезл ухаб диво вага иглу чача гель нате глас сгиб суша айда корт пляс свая веха дюна опус клич корн понт яуза амир сток болт паря тута хлев фарш свищ кина ишак арат синь тула торс альт трах сыта бейт тора рябь пеня эфес алан бола арба прыщ блат топь угон кляп съем увар хлоп наин оное фура сход ласт высь дора пюре вошь выть шлюз путы жары рать ахти эмир скоп баул цаца дуля шутя пике эссе енот упад скит сыск финн лжец шлак межа вона мяло хорь дюйм бард овал азот барк фора узда угар тога форт снос перл уран мхат олин юнга трак вояж убег меря резь поем овин аист соха ткач дерн наем жбан злак сват каир обух каюк урон панк плес плов гран ящер нома вымя ринк лама рожь табу зуев нега ромб плющ морж едок янки изюм кома желе шлаг обет нимб баск гурд киса кепи любя усть ввоз ролл буде слет джем фарс щепа золь бега тире олух отит клев ласа ложа аозт сума куща каюр слых гкчп шейх блюз идиш бриз копа бяка фанк лдпр мана навь пядь каин тятя клеш рейн шмон тлен кофр блеф быль лаос люто шлях барс бура сырт сеид весь арык норд аура увал гонг хина озон скак плав убой чита лоск арфа ширь кока кета сноб вето вест омск кача вязь мавр адан крит берн едко сома рань слив скок фант темя ярок стек течь гнус морс смак трио охра мета тета сляб морт скуп гурт хром овен тата мзда узко корь соты зело серб зыбь сонм бель улан гост ворс пенс кипу иена обод фифа торф юрин титр финт зева ушат хрящ клон харт опий деев тюря кунг понг стяг алоэ бэби зоря тать кряж сказ сена дюже лгун туша мкад пума змий слом олим джей ажур крат усач купа паяц каре дзот копь блиц эпос гиви аоот ковы сван форс гунн лань мята скиф шпик жмот пасс натр хаус маки софт шарм плут рувд лука гоби немо пшик сыто фарт биль маго сага неуч лафа кали пион буян галл бета эвон голо челн крой риза саго беня опал фиат апис лото тпру лясы хаки вить имам ярмо жито спас анри крен вьюн хота фикс сбег юшка гарт чтец темь глот овод таец куга вира новь кото коми анус леер аман щорс рагу драп хрыч блуд хлыщ краз чаво жмых швея виль руза вега вече".split(" ");
HashMap<String, Integer> dictSet = new HashMap<>(dict.length);
for (int i = 0; i < dict.length; i++) {
dictSet.put(dict[i], i);
}
int[][] graph = new int[dict.length][];
for (int i = 0; i < dict.length; i++) {
char[] word = dict[i].toCharArray();
ArrayList<Integer> adj = new ArrayList<>();
for (int j = 0; j < word.length; j++) {
char existingChar = word[j];
for (char ch = 'а'; ch <= 'я'; ch++) {
if (ch != existingChar) {
word[j] = ch;
Integer wordId = dictSet.get(new String(word));
if (wordId != null) {
adj.add(wordId);
}
}
}
word[j] = existingChar;
}
int[] adjArray = new int[adj.size()];
for (int j = 0; j < adjArray.length; j++) {
adjArray[j] = adj.get(j);
}
graph[i] = adjArray;
}
LinkedList<Integer> queue = new LinkedList<>();
int fromId = dictSet.get("слон");
int targetId = dictSet.get("муха");
queue.add(fromId);
int[] from = new int[dict.length];
Arrays.fill(from, -1);
from[fromId] = fromId;
while (!queue.isEmpty()) {
Integer wordId = queue.removeFirst();
for (int adjId : graph[wordId]) {
if (from[adjId] < 0) {
queue.addLast(adjId);
from[adjId] = wordId;
if (adjId == targetId) {
while (from[adjId] != adjId) {
System.out.print(dict[adjId]);
System.out.print('-');
adjId = from[adjId];
}
System.out.println(dict[adjId]);
System.out.println(System.currentTimeMillis() - start + " ms");
return;
}
}
}
}
System.out.println("Path not found.");
+1
добавил в качестве перехода появление новой буквы в произвольном месте слова
цепочка с максимальным приростом:
еж -> уж -> буж -> бук -> бок -> блок -> блик -> бзик -> узик -> узник -> ушник -> пушник -> путник -> путаник -> путание -> питание -> писание -> списание -> спивание -> спаивание -> опаивание -> опаливание -> осаливание -> оскаливание -> оскабливание -> поскабливание -> проскабливанное
ну и да, ничего сложнее BFS тут не нужно, конечно
цепочка с максимальным приростом:
еж -> уж -> буж -> бук -> бок -> блок -> блик -> бзик -> узик -> узник -> ушник -> пушник -> путник -> путаник -> путание -> питание -> писание -> списание -> спивание -> спаивание -> опаивание -> опаливание -> осаливание -> оскаливание -> оскабливание -> поскабливание -> проскабливанное
ну и да, ничего сложнее BFS тут не нужно, конечно
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как сделать из мухи слона