Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 22.11.2015, 19:08   #1
RegIon
Элита
 
Аватар для RegIon
 
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений
(для 1,012 пользователей)
Вопросы про A*

Тут возник вопрос как заставить алгоритм идти не по кратчайшему пути, а в определенном направлении.
Необходимо что бы он расчитывал с учетом направления из точки старта, но потом шел по кратчайшему.
Какую тут эвристическую функцию можно применить?
Еще желательно что бы на пути было меньше поворотов.



Просто машинка начинает разворачиваться на 180, чего совсем не нужно.

Я попытался так, но это не дает эффекта. Хотя по идее должно работать.
__________________
Сайт: http://iexpo.ml
(Offline)
 
Ответить с цитированием
Старый 22.11.2015, 19:15   #2
Nerd
Чудо-кот
 
Аватар для Nerd
 
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений
(для 1,471 пользователей)
Ответ: Вопросы про A*

А не вариант делать поиск пути по ориентированному графу, заранее определив направление граней, начиная от старта по известному направлению?
(Offline)
 
Ответить с цитированием
Старый 22.11.2015, 19:27   #3
RegIon
Элита
 
Аватар для RegIon
 
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений
(для 1,012 пользователей)
Ответ: Вопросы про A*

Я не совсем тебя понял.

Ну просто ситуация где однозначные пути.
Нужно провести путь сквозь зеленую точку.

Я понимаю, что нужно алгоритму сообщить, что повороты - тяжелая операция, и давай их по миниму, но хз как это сказать.
__________________
Сайт: http://iexpo.ml
(Offline)
 
Ответить с цитированием
Старый 22.11.2015, 19:59   #4
Nerd
Чудо-кот
 
Аватар для Nerd
 
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений
(для 1,471 пользователей)
Ответ: Вопросы про A*

Хз насколько я тебя понял. Если всё так просто:
1. Определяем ближайшую ноду от старта по нужному направлению
2. Двигаем к ней
3. Не даём поиску пути проходить через старт
Сообщение от RegIon Посмотреть сообщение
Я понимаю, что нужно алгоритму сообщить, что повороты - тяжелая операция, и давай их по миниму, но хз как это сказать.
Включай в стоимость вершины угол между ней и соседями.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
RegIon (23.11.2015)
Старый 23.11.2015, 11:17   #5
RegIon
Элита
 
Аватар для RegIon
 
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений
(для 1,012 пользователей)
Смущение Ответ: Вопросы про A*

Сообщение от Nerd Посмотреть сообщение
Хз насколько я тебя понял. Если всё так просто:
1. Определяем ближайшую ноду от старта по нужному направлению
2. Двигаем к ней
3. Не даём поиску пути проходить через старт

Включай в стоимость вершины угол между ней и соседями.
Я неправильно рассчитывал направление, из-за округления инта у меня направление = 0 всегда было.
Вторую пару скобок не поставил.
__________________
Сайт: http://iexpo.ml
(Offline)
 
Ответить с цитированием
Старый 01.01.2016, 22:34   #6
mingw
ПроЭктировщик
 
Аватар для mingw
 
Регистрация: 01.01.2016
Сообщений: 138
Написано 71 полезных сообщений
(для 155 пользователей)
Ответ: Вопросы про A*

Ввести понятие направление. Просто штрафуй те клетки, наступив на которую произойдет смена направления. Штрафовать можно путем тупого прибавления к стоимости шага G. Чем сильнее угол поворота, тем больше штраф.
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 02:40.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com