тактический
>т.е. любой пусть начинается либо с А
любой путь*
>чего-то одного не давно
не дано*
только сейчас в голову пришло. может просто всегда на каждом ответвлении иметь ввиду, что вторая точка А или В может быть вариантом ветвления? и например, когда алгоритм потратит все шаги при построении вариантов по левой стороне (как пример) и начнет возвращаться в предыдущий узел, чтобы построить по другой ветке (правее), он рано или поздно просто начнет параллельно строить варианты из второй точки старта... но это капец... я чувствую, что что-то не то делаю. не хочу придумывать велосипед. поэтому, если такие алгоритмы есть, то хотелось бы почитать про них. но я пробовал искать - не смог
лол. или просто объединить все стартовые точки одной? чтобы в каждый узел не дублировать ветку для А или В
Что такое "путь" в твоей задаче?
Обычно под этим понимают последовательность вершин, любые две соседние из которых соединены ребром. То есть это нечто связное по определению. На втором пике у тебя какая-то несвязная хуйня. Конкретизируй, что сделать нужно.
Поскольку у тебя число шагов фиксировано, то такое объединение будет не очень удобным. Тебе всё равно придётся трекать, прошёл ли ты по фейковому ребру или нет, чтоб не считать это за попытку.
не совсем понял. что значит по фейковому? в начало проверок нужно добавить проверку на количество шагов, если они достигнуты, то вернуться обратно и выбрать другой вариант. если вариантов больше нет, то спускаться вниз, не сбрасывая уже пройденные и искать первую доступную ветку. правда потом придется обратно подниматься в то место каким-то образом, чтобы откатывать уже пройденные узлы и так же искать новые доступные вершины.
> по фейковому
Фейковыми я называю рёбра инцидентные добавленной вершине S на твоей картинке.
> в начало проверок нужно добавить проверку на количество шагов, если они достигнуты, то вернуться обратно и выбрать другой вариант.
Допустимое количество шагов в своём новом графе с добавленной вершиной S ты каким предлагаешь сделать?
играл в пое? там есть дерево навыков. начинать можно с нескольких точек ветвление. на реальном примере это 123 шагов (т.е. 123 очка умений) и огромный граф. хотел написать генератор билдов. но вообще, я вот потом подумал, что это ахереть сколько комбинаций и без квантового пк тут никак.
ДАЛЬШЕ ИГРОВОЙ СЛЕНГ ИСПОЛЬЗУЕТСЯ: ведь каждое число комбинаций только в дереве это уже много умноженное на число вариантов с гемами умноженное на число комбинаций с гемами умноженное на число комбинаций шмоток * умноженное на число комбинаций аффиксов редких шмоток... короче я взгрустнул.
вообще, задача была изначально сгенерировать все варианты, прогнать их через программу (path of building), которая посчитала бы все статы (дпс, резисты, хп...) и после всего отсортировать по нужным резистам, а потом брать на вооружение билд и играть.
>Допустимое количество шагов в своём новом графе с добавленной вершиной S ты каким предлагаешь сделать?
можно просто начать с -1 или сделать проверку на N + 1
И это неправильно. Если ты прошёл только по одному фейковому ребру, то проверку-то тебе на N нужно делать.
Да, с глубиной 123, если я правильно понял о чём речь, ты, конечно, ничего не переберёшь. Если ты сможешь более формально без игрового сленга сформулировать, что там происходит и что хочется сделать, то можно будет подумать, можно ли твою задачу решить без перебора.
я хотел считать не по ребрам а по вершинам (узлам). т.е. когда алгоритм только начинается (вершина S), текущий счетчик шагов равен -1. если алгоритм работает рекурсивно через левую сторону, то попадаем в вершину A и счетчик равен 0. но мы как бы стоим еще на вершине, а не проходим ее (т.е. не берем очко умение, я тут описал реальную задачу ). далее просто алгоритм работает до тех пор, пока не достигнем нужное число шагов, либо не попадем в тупик.
1. если достигли числа шагов, отменяем последний узел и ищем другой вариант на этом уровне. если вариантов на нем нет, то отнимаем снова (возвращаемся назад) и т.д.
2. если достигли тупика, то нужно будет НЕ отнимая пройденные вершины, спускаться вниз, помечая пусть, чтобы потом в него вернуться. спускаемся таким образом вниз, пока не найдем ответвление и не наберем все нужные шаги.
>помечая пусть, чтобы потом в него вернуться
помечая путь, чтобы потом вернуться обратно в ту вершину и начать уже отнимать пройденные вершины
фикс + уточнение
> я хотел считать не по ребрам а по вершинам (узлам).
Какая разница? Представь, что у тебя исходное заданное число шагов = 1. Ты прилепил свою вершину S. Исходное число шагов выставил в -1 и будешь сверять его с 1+1 = 2. Таким образом, ты допустим проходишь в A (число шагов = 0), потом идёшь по красному ребру со второго пика (число шагов = 1) и потом идёшь ещё по одному красному ребру (тут число шагов становится равным 2 и ты прекращаешь). Итого, ты сгенерировал путь длины 2, а не длины 1.
> отсортировать по нужным резистам
Что такое резист?
ну, я попытаюсь... вот пример (пик 1): мы построили путь из 12 шагов и открыли пустое гнездо, куда можно вставить предмет. но предмет не один, а скажем... предметов 100. т.е. это 10 вариантов только для этой ветки из 12 узлов.... но герой, помимо дерева навыков, еще носит на себе предметы (нагрудный доспех, сапоги, ремень, перчатки, шлем и т.д.), таких слотов для каждого типа предмета в игре 10 (пик 2). и в каждый этот слот можно засунуть еще по 100+ вариантов предметов каждого типа (т.е. 100+ перчаток, 100+ оружия). я конечно не точные цифры называю, но их действительно в игре много... скажем, для каждого типа предмета из 100+ предметов есть 20 предметов, которые могут иметь разные свойства. всего таких свойств может быть 6, а вариантов свойств может быть порядка 50+. но у игрока еще есть умения, которыми он атакует. в игре есть, скажем, 100+ таких умений, но каждое умение еще можно усилить 5 умениями-поддержки. а вариантов таких умений поддержки еще 100+... я не уверен, стоит ли продолжать? ведь это только на примере 12 шагов, а их должно быть 123 и плюс тех пустых гнезд может быть тоже не одно, а штук 10+. так же у игрока может быть 5 баночек зелий, всего таких баночек в игре тоже порядка 100+
сопротивление урону. например огненный резист (сопротивление урону огня). эта сортировка нужна для того, чтобы не только по урону в секунды искать билд, но и еще с учетом хорошей выживаемости.
так нет же, я же написал, либо начинать с -1, ЛИБО сверять с N + 1, но тогда начинать с 0 конечно. или начинать с -1 и сверять с N
>т.е. это 10 вариантов только для этой ветки из 12 узлов....
100 вариантов*
фикс
Пусть число допустимых шагов = 2. Описанный тобой алгоритм сможет сгенерировать "путь", состоящий из одного ребра, торчащего из A, и из одного ребра, торчащего из B?
Если да, то как это произойдёт?
А задача в итоге найти оптимальную в некотором смысле конфигурацию? А как эту оптимальность замерять?
начали с S(-1), пошли в A(0), потом в А2(1), потом в А3(2), число шагов достигнуто ищем другой путь.
вернулись в А2(1), потом в А4(2), число достигнуто, ищем другой путь.
вернулись в А2(1), вариантов нет (тупик), возвращаемся в А(1) не отнимая шаги + сохраняем маршрут, чтобы вернуться, попали в S(1), нашли вариант B ( тут проблема, получается, когда в S возвращаемся, надо -1 отнимать от шагов, чтобы попав в B была (1) ), далее идем в B1(2), путь построен, теперь по маршруту, который сохраняли, возвращаемся обратно в A(2) и отнимаем, возвращаясь в S(-1) и строим дальше для B(0), B2(1), B3(2) <- этот узел не учитывается, т.к. идет возврат на проверке. ну и возвращаемся в S(-1). алгоритм завершен.
еще вторая проблема - дублируются пути. надо будет подумать...
да, нужно найти хорошее соотношение урона в секунду, уровня здоровья и защитных характеристик. в игре приемлемый уровнем здоровья можно считать 4000 (можно и 3000, тут от рук уже все зависит ну и от билда), 3 характеристики защиты минимум 60% каждая, ну и урона чем больше тем лучше, никогда не помешает. хп и защиты это тоже касается, лишними не будут, но минимальный порог примерно такой. я планировал это все просто отсортировать по убыванию сначала по урону, потом по хп, потом по резистам. и там уже дальше смотреть первые, скажем, топ 100 вариантов вручную и проверять
>далее идем в B1(2)
в В2(2)*
фикс
>возвращаемся обратно в A(2) и отнимаем
так, что-то я ошибся. мы возвращаемся в S, отнимая от счетчика -1 потому что мы ищем другой вариант, и еще -1 отнимаем потмоу что попадаем в S. но тогда получается S(0), а не -1.
а, ну все правильно, у нас же B взято, поэтому S(0) + 1 и попадаем в B2(1) и дальше его уже достраиваем B3(2).
вариант не особо удобный для восприятия, запутался немного
> тут проблема
Ну вот именно. Причём проблема ровно та, о которой я тебе в первом сообщении и написал: тебе приходится специальным образом учитывать рёбра, идущие из S. Таким образом, добавление этой вершины тебе не помогает, а только мешает.
В общем, аккуратно этот перебор делается примерно так. Тебе нужно поддерживать текущий набранный подграф. Изначально он состоит только из двух вершин: A и B. Находясь в текущем состоянии, ты перебираешь все возможные рёбра, инцидентные твоему подграфу (но ещё не лежащие в нём) и для каждого такого ребра пытаешься добавить его в свой подграф и рекурсивно вызвать процедуру поиска для этого нового подграфа. Естественно нужно следить за кол-во набранных рёбер. Как только набрал нужное кол-во рёбер - ты в терминальном состоянии. Сохраняешь его в результирующий список и откатываешься до родительского подграфа.
> еще вторая проблема - дублируются пути. надо будет подумать...
Да, такая проблема есть и ничего умнее, чем хранить таблицу с подграфами, которые тебе уже встречались в процессе поиска, тут не придумаешь скорее всего.
Но ещё раз. Такого сорта переборы осмысленно делать только с очень маленькой глубиной. А это явно не твой случай.
не особо понял алгоритм. вот у меня 2 вершины А и В. они не связаны между собой. так же у меня есть полный граф. я смотрю по этому графу, ориентируясь на подграф, какие вершины соединены с вершиной А. в моем случае это А2, т.е. шагов стало 1 при условии, если начал с 0. затем смотрю для В, это В2, шагов стало 2. теперь отменяю для В шаг, получаю A2(1).
теперь мой подграф это А2? смотрю с какими вершинами соединены А2, это А3 и А4. иду в А3(2). путь построен, возвращаюсь в А2(1), иду в А4(2). так? но тогда все равно дублируется путь.
>Такого сорта переборы осмысленно делать только с очень маленькой глубиной
я бы мог и денек другой даже подождать,но тут да, похоже на годы вычислений...
Тред не читал, но чому просто не найти все пути из А сперва, а потом все пути из Б?
Ведь тебе надо найти все разные пути фиксированой длины, они очевидно будут разные, т.к начинаются с разных вершин.
Ведь тебе надо найти все разные пути фиксированой длины, они очевидно будут разные, т.к начинаются с разных вершин.
> теперь мой подграф это А2?
Теперь твой подграф состоит из отдельно стоящей вершины B и вершин A и A2, соединённых ребром. Дальше ты смотришь, что какие там ещё рёбра инциденты этому подграфу. Но ты эти рёбра в своём сообщении правильно перечислил.
> но тогда все равно дублируется путь.
Да. Как этого избежать, я написал. Нужно хранить таблицу состояний, в которых ты уже находился и когда ты вызываешь поиск для очередного подграфа, нужно проверять по этой таблице, не находился ли ты уже в таком состоянии ранее. Если находился, то сразу откатываться.
Потому что его не пути, а подграфы, содержащие эти две вершины, интересуют.
Конечно, всё ещё можно искать эти подграфы независимо для обеих вершин, но их в конце всё равно придётся попарно комбинировать.
теперь понял, кажется. спасибо. правда какой смысл уже?) если все равно такое не вычислить... кстати, у амазона же вроде есть вычислительные сервера какие-то? может быть на них возможно?... но вряд ли конечно...
Забей на перебор - это бесперспективно. Никакие кластеры тебе не помогут. Кластеры имеют смысл, когда у тебя какая-нибудь распределённая задача, которая параллелится хорошо. А тут у тебя shared state в виде таблицы состояний, которые весь параллелилизм портит. Ты, конечно, можешь как-нибудь поизъёбываться и попытаться это распаралеллить, но с такой глубиной тебе это всё равно не поможет.
На твоём бы месте я лучше потратил время на какие-нибудь приближённые методы, эвристики и тому подобные вещи. Только для начала нужно чётко для самого себя сформулировать, какой таргет ты оптимизируешь.
я тут подумал, может по частям все делать? например найти все варианты для глубины (например 10), найти лучший вариант (только для дерева, без предметов которые носит игрок), потом для этого варианта ветвления продолжить в ту же глубину 10 искать другой лучший вариант и так до тех пор, пока не дойду до 123. затем на основе одного варианта ветвления дерева уже надевать на героя шмотки, комбинируя их (можно будет тоже подумать как лучше сделать). это наверное и есть то, о чем ты сказал? >приближённые методы, эвристики и тому подобные вещи
Из условия задачи не понятно, допускается ли посещать уже посещенные точки при поиске "маршрута"?
И вообще, имеет ли эта задача под собой какое-нибудь практическое применение, или же это просто некая теоретическая головоломка?
Олимпиадник и некогда поезадрот в треде, поясняю за задачу.
Есть множество скилов которое доступно для выбора персонажу. Всего скилов около 400, если память не изменяет, скиллпоинтов около 120.
Задача ОПа - перебрать подмножество мощности 120 этого множества скилов, для каждого подмножества перебрать основные варианты шмоток персонажа и засунуть в функцию скоринга, дабы потом выбрать несколько лучших вариантов.
Теперь суть - во первых, количество вариантов только выбора скилов - это количество поддеревьев размера 120 в графе из 400 вершин. Это величина по порядку очень близкая к С из 400 по 120. Одно это ставит крест на идее перебора, но дальше это умножается на количество комбинаций шмоток, которое не менее астрономическое, а потом умножается на время вычисления скоринговой функции. А скоринговая функция это литературно симуляция n минут долбления моба в игре, занимающая секунд 10 на среднем пека.
Короче, перебирать всё это ты будешь до тепловой смерти вселенной.
Я бы на твоём месте либо отказался от этой идеи и получал удовольствие от игры вместо минмакс задротства удовольствие в ПОЕ, лол, ебало Криса имаджинировали? либо запилил какую-то параметрическую стратегию выбора дерева скилов и шмоток, и оптимизировал уже её какой-то генетикой, например.
да я довольно сразу отказался от этой идеи перебором. еще с этого поста своего
но даже то, о чем в нем я писал, я не реализовал. где-то неделю еще я думал как это все взвесить, как лучше определить алгоритм и т.д. в итоге думал-думал, ничего не придумал толкового и плюнул. к тому же, новая лига, которую лысый высрал, мягко говоря отбило желание иметь что-то общее с этой игрой (пока что, а там посмотрим...). а вообще задача, да... такое перебором точно не вычислить. надо придумывать критерии фильтрации вероятно лучших значений, но это уже будет не точно и не со 100% гарантией.
а общая идея была в том, чтобы сгенерировать себе оптимальный (секретный) билд, собрать его за обрывок свитка и пойти выносить ендгейм, лол. или хотя бы обнаружить, возможно, действительно уникальный и секретный билд, казалось бы, для мертвого (не метового) скила.
условие: за ограниченное число шагов (например 6), но при этом число фиксировано, и не может быть меньше (все шаги должны быть пройдены), показать все возможные варианты. при чем, нет такого понятия как поиск путей в графе, т.к. нет конечной точки и нет определенной стартовой (т.к. повторю, начинать можно с обеих точек, чего-то одного не давно). 1 шаг - 1 посещение узла. узлы А и B тоже учитываются в общем количестве шагов.
основная проблема в том, что точек начала несколько, а значит могут быть и такие варианты (2 пик). и я вообще не могу представить как это можно все учесть и написать.