Распараллеливание A * для дорогого вычисления стоимости
То, что для меня решило, делает 2 вещи: 1. Создайте нового пользователя, кроме root, с помощью некоторого пароля, используя следующие команды:
CREATE USER 'newuser'@'localhost' IDENTIFIED BY 'password';
GRANT ALL PRIVILEGES ON *.* TO 'newuser'@'localhost';
FLUSH PRIVILEGES;
2. комментарий IP-адрес на mysqld.conf
, затем подключиться с новым именем пользователя и паролем. он должен работать.
1 ответ
Существует две вещи обсудить в ответе. Первой является алгоритмическая эффективность. Вторым является параллелизм.
существует научно-исследовательская работа , который изучает этот случай и создает* вариант, DEA*. Это использует дешевую допустимую эвристику на граничной стоимости для получения нижней границы на стоимости преемников и затем только вычисляет фактическую стоимость края, когда показано, что преемник мог быть на оптимальном пути.
Обычно* разворачивает узел путем (1) генерации преемников с их новой f-стоимостью и (2) размещения их в открытый. DEA* алгоритм (1) генерирует преемников с предполагаемым (нижние границы на) f-затраты и (2) размещает их в открытый. Если состояние удалено из открытого только с f-оценкой-затрат, точный edge/f-cost вычисляется, и состояние помещается назад на открытом.
Это - вариант общего представления о Частичное Расширение , и , другая работа исследовала дорогую граничную проблему также.
В этой модели, можно постараться не вычислять много дорогих краев, который полезен. Но, все еще было бы полезно вычислить остающиеся края параллельно. В зависимости от точной стоимости существует много способов сделать это. Если Ваш открытый список является многопоточным, он может вычислить граничные затраты каждый раз, когда состояние добавляется для открытия. Но, было бы более эффективно по существу иметь две приоритетных очереди.
Одна приоритетная очередь содержала бы состояния с их граничными затратами, вычисленными, и другой будет содержать тех, которым нужно сделанное вычисление. Параллельный код может быть написан, чтобы взять состояния от очереди с более низким приоритетом и вычислить их граничные затраты, добавив их к первой очереди, когда они завершены. Затем обычная программа может обработать состояния от первой очереди в регулярном первоочередном заказе.
ключевой пункт - то, что параллельная часть может сфокусироваться на вычислительных граничных затратах для состояний, которые собираются быть расширенными затем вместо того, чтобы делать все состояния, поскольку они добавляются к очереди.
Примечание, что процесс как это мог привести к исследованию более длинного пути перед более коротким путем, обнаружено. Так, необходимо отслеживать то, когда Вы находите более короткий путь к состоянию (на открытом или закрытом) и удостоверяетесь, что перемещаете состояния от закрытой спины для открытия, когда более короткий путь обнаружен.
Связанный с этим, Вы не можете завершить, после того как Вы находите решение - это не обязательно будет оптимально. Необходимо закончить разворачивать любые состояния, которые имеют f-стоимость ниже, чем решение, которое Вы нашли. (Можно отбросить любые состояния, которые имеют стоимость решения, больше, чем или равный найденному решению.) [Отмечают, что я дал общее направление на хороших подходах здесь; если Вы застреваете в определенных деталях, можно попросить разъяснение.]