0. RonX01 189 09.07.19 12:40 Сейчас в теме

Алгоритмы поиска пути в графе

Реализуем алгоритмы поиска пути в графе на платформе 1С 8.3, такие как алгоритм А*, поиск в ширину, жадный поиск, алгоритм Дейкстры и вконце волновой.

Перейти к публикации

Лучшие комментарии
1. RonX01 189 09.07.19 12:08 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
Спецификация.pdf
wolfsoft; suepifanov; headMade; NeviD; login1020; tsukanov; Jeka44; Boo; sam441; kuzyara; pm74; khomkolov; user1004034; wowik; товарищ Ын; user764477; +16 Ответить
4. RonX01 189 10.07.19 11:14 Сейчас в теме
(3) Добавил волновой алгоритм. Спецификация обработки осталась прежней
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
pchelkatoo; headMade; +2 Ответить
Остальные комментарии
Избранное Подписка Сортировка: Древо
1. RonX01 189 09.07.19 12:08 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
Спецификация.pdf
wolfsoft; suepifanov; headMade; NeviD; login1020; tsukanov; Jeka44; Boo; sam441; kuzyara; pm74; khomkolov; user1004034; wowik; товарищ Ын; user764477; +16 Ответить
2. informa1555 1072 09.07.19 15:55 Сейчас в теме
И не далее как пару недель назад : https://infostart.ru/public/1081085/)))
for_sale; +1 Ответить
3. aximo 805 09.07.19 17:26 Сейчас в теме
Замечательно! Можно взять алгоритм не «выдумывая» его)))))

А как на счет волнового алгоритма?
4. RonX01 189 10.07.19 11:14 Сейчас в теме
(3) Добавил волновой алгоритм. Спецификация обработки осталась прежней
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
pchelkatoo; headMade; +2 Ответить
5. it@contlog.ru 12.07.19 06:42 Сейчас в теме
хорошо, будет ли пример jump point search?
6. RonX01 189 12.07.19 07:30 Сейчас в теме
(5) Пока пас. Может быть позже.
7. it@contlog.ru 12.07.19 12:01 Сейчас в теме
Тогда еще спрошу. В случае если есть несколько точек Б интересно какая из них ближайшая. Какой из них предпочтительней?
8. RonX01 189 14.07.19 09:15 Сейчас в теме
(7) При поиске в ширину можно добавить несколько вершин, тогда функцию можно расширить так:
Дополнение к коду

В результате мы получим карту с потоками до вершин. Т.е. зная вершину где мы находимся, используя такую карту мы сразу движемся в ближнюю точку (карта прикреплена ниже).
Если же необходимо предварительно знать размеры пути, то это будет похоже на волновой алгоритм, только волны будут расходиться от точки А, и поскольку там хранятся номера волн, то в каждой точке Б будет номер волны, и чем меньше номер, тем путь до точки Б ближе.
Но это не подойдет для жадного поиска и алгоритма А*.

ПС: Похоже надо делать продожение, где реализовать алгоритмом jump point search и возможность указывать множество точек Б.
Прикрепленные файлы:
10. it@contlog.ru 18.07.19 05:13 Сейчас в теме
(8) Точно!!! Про продолжение согласен.
9. wolfsoft 2420 15.07.19 08:04 Сейчас в теме
Дельная вещь, однозначно в копилку, и плюс от меня.
Оставьте свое сообщение
Новые вопросы с вознаграждением
Автор темы объявил вознаграждение за найденный ответ, его получит тот, кто первый поможет автору.

Вакансии

Бизнес-аналитик 1С
Москва
зарплата от 140 000 руб. до 200 000 руб.
Полный день

Программист 1С
Санкт-Петербург
зарплата от 120 000 руб.
Полный день

Консультант 1С (Бухгалтерия)
Санкт-Петербург
зарплата от 100 000 руб.
Полный день

Программист 1С
Санкт-Петербург
зарплата от 150 000 руб.
Полный день

Программист 1С
Тюмень
зарплата от 70 000 руб.
Полный день