метод ветвей и границ , интересно мнение

вот объяснил нам лектор сабж. один из походов при продолжении ветвления - это выбор наиболее "перспективной" вершины, т.е. с наменьшей(наибольшей) оценкой. я его спросил, а не получается, что мы меняем шило на мыло, т.е. есть ли смысл таким образом делать - не проще ли перебирать вершины дерева по порядку, т.к. при выборе перспективных вершин надо по-большому счету делать их сортировку, а это ведь тоже кушает время, а при всем притом не совсем обязательно, что при выборе "перспективной" вершины мы получим какую-то минимальную оценку, ведь это же по-большому счету эвристика.
буду благодарен за любые мнения.

такой подход можно охарактеризовать как поиск в глубину, в отличае от способа предлогаемого тобой - поиска в ширину. Поиск в ширину находит наикротчайшей путь к цели, но съедает больше ресурсов, поиск в глубину при правильной отценке найдет путь к цели за более быстрое время, и чем точнее отченка тем он будет ближе к пути выбранному алгоритмом в ширину. Отценка это конечно же эвристика.

2 Sazabis ваш ответ правильный но помоему не на поставленный вопрос.

2 спрашивающий.

Сортировку делать не обязательно некоторые слабые ограничения сделают так что примерно вполовине случаев ты сЭкономишь на просматривание лишних нодов.

это все равно оставит сложность экспоненциальной но может уменьшить объём работы в два раза

разумеется в худшем случае нет
и разумеется сортировка это не слабое ограничение

esperanto,
спасибо за ответ, но я мало что понял из твоего ответа. можно чуть пободробней, просто для меня предложения кажутся отрывочными и несвязаннными друг с другом.

когда ты выбираешь ветвь предполагается что ты будешь ее раскручивать до определенной глубины ?. Тогда, когда ты выбрал ветвь которая идет первой в списке, ты будешь обрабатывать все ее ветвления и только потом вернешся к анализу второй ветки в начальном списке. Если решение задачи будет найдено в какой нибудь подветке, то, дальнейший анализ становится излишним. => чем раньше ты выберешь "счастливую" ветку тем быстрее ты придешь к цели. В зависимости от глубины анализа, сортировка становится эффективнее.

предположим что ты ищещь минимум у пока минимальное значение котороы ты нашел =5
и сейчас ты заходишь в нод с детьми

1) отсортированый (30, 50, 80) так как твой противник максимум то ты сразу же видишь что он минимум получит 30 а твой мин=10 поэтому дальше т.е 50, 80, можно не просматривать
это идиальный отсортированный случай


2) наихудший случай
(1 2 3 6 7 9 15)

твой противник максимум поэтому 1,2, 3, 6, 7 тебе не очем не говорят ты вынужден идти до конца и найдя 15 понимаешь что этот нод тебе не выгоден так как у тебя уже есть минимум 10


3) средний случай случайный
(1, 3 , 15, 5 ,6 23 54)

ты дошел до 15 и можешь обрубать ибо максимум в любом случае даст тебе больше или равно 15 а у тебя уже есть 10

если не понятно
зайди в аи в нардах я там давал ссылку parol=daphna or dafna
там есть рисунки

спасибо еще раз. мне понятно, что сказал Sazabis.
мне интересно, что чего стоит: то ли не сортировать, то ли сортировать.
ведь при сортировке тратится время,но мы почему-то надеемся, что, выбирая минимум, мы в итоге быстрее найдем минимальную ветвь, а без сортировки у нас на неё время не тратится и, как я считаю вероятность найти ветку с весом поменьше ни чуть не меньше, чем при выборе минимума, так как одному Богу ведомо, что за дети у этого нода (узла).
я это написал все это, потому что не очень понял esperanto, т.е. не нашел соответствия между моим вопросом и ответом: вроде бы я спросил одно, а ты мне объяснил,как все это работает. я вывода не понял просто.

вывод сортировать нет смысла
вывод при случайном расскладе время уменьшится в среднем в два раза
вывод при некоторых слабых ограничениях можно уменьшить еще в несколько раз
вывод все равно сложность экспоненцальная

вывод вроде бы все я это уже написал

вывод я тоже понял что сказал З.

спасибо. теперь мне все стало ясно.
вывод: я понял то, что ты сказал.

)

Весь вопрос можешь ли ты оценить ветвь на перспективность или нет