Публикации по теме 'backtracking'
Аддитивная игра (часть III): реализация
Надеюсь, к этому моменту нам удалось убедить себя в том, что решения этой головоломки существуют и их можно найти, по крайней мере, путем тщательного поиска. Но одно дело сказать, что вы можете что-то сделать, и совсем другое - сделать это на самом деле.
В этой третьей части серии я надеюсь представить приемлемый программный метод нахождения всех решений головоломки. Подход, который я выберу, имеет красивое название Поиск с возвратом , но должен быть легким в использовании даже без..
Вопросы по теме 'backtracking'
можно ли избежать возврата при попытке минимизировать пространство прямоугольника, которое заключает в себе прямоугольники различных целочисленных форм?
Абстракция моей проблемы заключается в том, что на декартовой плоскости много прямоугольников. Эти прямоугольники имеют известные целочисленные размеры и должны иметь целочисленные координаты, их абсциссы (горизонтальные координаты) известны и...
124 просмотров
schedule
03.10.2022
CUDA: остановить все остальные потоки
У меня есть проблема, которая, казалось бы, решаема путем перечисления всех возможных решений, а затем поиска лучшего. Для этого я разработал алгоритм поиска с возвратом, который перечисляет и сохраняет лучшее решение, если оно найдено. Пока...
3497 просмотров
schedule
17.03.2022
Динамическое построение дерева с рекурсивным возвратом
У меня есть эта проблема, что мне нужно решить проблему рекурсивного возврата. Она очень похожа на проблему n ферзей, но отличается тем, что в ней используются разные кандидаты на асимметричной доске. Всего есть четыре разных кандидата, каждый из...
1374 просмотров
schedule
14.02.2023
Проблема с рекурсивным возвратом
Привет, ребята, недавно написал о проблеме с моим алгоритмом.
Поиск чисел из набора, которые дают минимальное количество отходов
Я немного изменил код, так что теперь он в какой-то степени откатывается назад, однако вывод по-прежнему ошибочен....
1263 просмотров
schedule
22.03.2022
Как преобразовать алгоритм возврата в поток?
Есть ли способ определить stream с алгоритмом backtracking в Scala?
Например, следующий алгоритм backtracking печатает все «двоичные» строки заданного размера.
def binaries(s:String, n:Int) {
if (s.size == n)
println(s)
else {...
710 просмотров
schedule
13.03.2023
В поисках лучшей системы возврата
Я попытаюсь объяснить это простыми словами, потому что это, вероятно, короче, чем если бы я отправил код. Я сделал часть рекурсивного решения, которое должно завершить игру, выбрав правильный «порядок ходов», и если оно зайдет в тупик, то оно должно...
150 просмотров
schedule
08.06.2023
Рекурсивный возврат судоку, слишком ранний возврат
Итак, я пишу решатель судоку на С++ и столкнулся с небольшой загвоздкой. Ниже приведен код моей платы решения. Он работает для первых 3 рядов головоломки, но не повторяется при попадании в конец 4-го ряда. Глядя на код на gdb, он попадает в конец...
648 просмотров
schedule
03.05.2022
Алгоритм восьми ферзей
Ранее я задавал вопрос о решении проблемы восьми ферзей с помощью Java. У меня есть алгоритм обратного отслеживания для решения проблемы.
Я пытался использовать этот алгоритм, но не знаю, что не так с моим кодом. Он размещает только до 7 ферзей....
19369 просмотров
schedule
26.07.2023
C++: рекурсивная сетка boggle с возвратом назад
Я понимаю, что этот код может быть немного сложным для чтения, я пытался адаптировать стандартный алгоритм рекурсивного решения лабиринта, где все направления перебираются до тех пор, пока не будет найдено решение, к алгоритму для игры «boggle»....
1879 просмотров
schedule
06.05.2022
Алгоритм N+1 ферзя
Я хочу улучшить скорость моего алгоритма для вычисления количества решений проблемы N+1 ферзей (поместите N+1 ферзей на NxN шахматную доску с 1 пешкой). Я в основном использую брутфорс в сочетании с откатом, я сначала ставлю пешку на случайное...
353 просмотров
schedule
09.04.2024
Сохранить переменную при возврате пролога
Я пытаюсь найти минимальную стоимость пути, сохраняя переменную Min при отслеживании с возвратом. Приведенный ниже код не работает, однако он дает некоторое представление о том, что я хочу.
Min - это переменная, которая содержит текущее...
686 просмотров
schedule
18.02.2023
Возврат в Standard ML
Я видел в своем руководстве по SML следующую функцию, которая вычисляет, сколько монет определенного вида необходимо для конкретной сдачи. Например, change [5,2] 16 =[5,5,2,2,2] , потому что с двумя 5-монетами и тремя 2-монетами получается 16....
967 просмотров
schedule
31.01.2024
нужна помощь в исправлении этого кода при динамическом программировании/рекурсии при вычислении минимальных монет с использованием Java
У меня есть мой код, который предназначен для возврата минимальной конфигурации монет для внесения сдачи на заданную сумму. Он принимает два параметра, сумму и список номиналов. У меня нет ошибки компиляции, и программа работает, чтобы выдавать...
363 просмотров
schedule
18.06.2023
Можете ли вы написать между / 3 в чистом прологе?
Я пытался понять, как создать серию значений из предиката Prolog при возврате. Встроенный предикат between/3 будет генерировать все целые числа в диапазоне по одному при поиске с возвратом, поэтому пример того, как это написано, может помочь мне в...
6728 просмотров
schedule
28.04.2022
Алгоритм проверки игры-головоломки с прогулкой по сети
Каков простейший алгоритм проверки того, что все соединения были успешно установлены и все соединения закрыты?
Я положил игровые плитки, и игра готова к игре, все, что мне нужно, это алгоритм для проверки и внесения изменений в соединения, когда...
254 просмотров
schedule
11.07.2023
Алгоритм упаковки в корзину нуждается в ускорении
Я ищу разумный способ подойти к варианту распространенной проблемы с упаковкой в мусорное ведро. Учитывая количество сумок (как я их называю) определенной вместимости и список предметов, занимающих определенное пространство, задача состоит в том,...
4122 просмотров
schedule
18.12.2022
Как рассчитать временную сложность алгоритма возврата?
Как рассчитать временную сложность для этих алгоритмов поиска с возвратом и имеют ли они одинаковую временную сложность? Если отличается как? Пожалуйста, объясните подробно и спасибо за помощь.
1. Hamiltonian cycle:
bool...
61839 просмотров
schedule
24.05.2023
Рюкзак Ветвь и Связанный
У меня есть следующие данные:
item weight value value/weight
1 5 40 8
2 2 10 5
3 6 30 5
4 1 12 12
5 2 18 9
Емкость равна 10. Как продолжить расчет...
2003 просмотров
schedule
18.04.2023
Предотвращение возврата после первого решения пары Фибоначчи
Термин fib(N,F) верен, когда F является N числом Фибоначчи.
У меня обычно работает следующий код Пролога:
:-use_module(library(clpfd)).
fib(0,0).
fib(1,1).
fib(N,F) :-
N #> 1,
N #=< F + 1,
F #>= N - 1,
F #> 0,
N1...
1209 просмотров
schedule
22.05.2023
Рекурсивный возврат в древовидной структуре
У меня есть этот алгоритм, и я хочу реализовать поиск по графу, используя рекурсивный поиск с возвратом.
Прежде всего мой код:
public static boolean buildTree(GenericTreeNode<String> inputNode){
while(!interruptFlag)
{
try...
1284 просмотров
schedule
23.10.2022