Перебор

← →
Gydvin © (2006-01-31 11:18) [0]

Привет all тут проблема возникла с перебором. вот код

procedure TForm1.Button1Click(Sender: TObject); var list,list1,list2:tstringlist; a,t,x,y:integer; r:array of string; s,s1:string; label ik; begin a:=5; setlength(r,a+2); list:=tstringlist.Create; list1:=tstringlist.Create; list2:=tstringlist.Create; //list.LoadFromFile("file.txt"); ///текстовый файл с нобором строк x:=0; while x<a do begin inc(a); ik: ///// s:=der(x); здесь мы получаем маску слова s:="п?ляна";///например вот эту маску; list1.Clear; list2.Clear; t:=length(s); //здесь получаем список строк подходящих по длине к маске (s) for y:=0 to list.Count-1 do begin s1:=list.Strings[y]; if length(s1)=t then list1.Add(s1); end; list2.Text:=r[x]; //// сюда грузим слова уже раннее проверенные ////здесь удаляем из списка ранее проверенные for y:=0 to list2.Count-1 do begin s1:=list2.Strings[y]; t:=list1.IndexOf(s1); if t>-1 then list1.Delete(t); end; list1.Clear; ////здесь получаем слова подходящие по маске for y:=0 to list1.Count-1 do begin s1:=list1.Strings[y]; for t:=1 to length(s1) do if s[t]="?" then s1[t]:="?"; if s1=s then list2.Add(list1.Strings[y]); end; /// здесь выбираем слово из списка randomize; s:=list2.Strings[(list2.Count)]; // если слова не оказалось, тоесть нет вариантов if s="" then begin r[x]:=""; ///, мы возвращаемся на шаг назад dec(x); if (x<1)or(x=1) then begin showmessage("Были прверены все варианты"); exit; //здесь выходим если больше назад вернутся неможем end; goto ik; end; ///здесь есль слово все же есть мы проделываем с ним определенные //действия /// и скидываем его в использованные r[x]:=r[x]+s+#13#10; ///сохранение проверенного слова end;

А вот, что конкретно не устраивает, по мере наполнения r[x], алгоритм начинает тормозить, да и плоско как то (r[x]:=r[x]+s+#13#10) это выглядит. И вобще алгоритм медленный, короче одним словом плоский, может кто знает как сделать это лучше или какие предложения будут, я непротив, а то уже голову сломал, а путевого ничего придумать не могу.

← →
Gero © (2006-01-31 11:23) [1]

Что делает этот код?

> да и плоско как то

> одним словом плоский

Это как?

← →
Gydvin © (2006-01-31 11:23) [2]

Ой, опечатка

list1.Clear;
////здесь получаем слова подходящие по маске

надо

list2.Clear;
////здесь получаем слова подходящие по маске

← →
Вольный Стрелок © (2006-01-31 11:25) [3]

точно перебор
перебрал, наверно, автор

← →
Gydvin © (2006-01-31 11:27) [4]

Это огызок процедуры заполнения кроссворда,сканворда из текстового словаря, пишу компоненту ну и собственно программу

← →
Gero © (2006-01-31 11:28) [5]

> Gydvin © (31.01.06 11:18)

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

← →
Gero © (2006-01-31 11:29) [6]

> Gydvin © (31.01.06 11:27)
> Это огызок процедуры заполнения кроссворда,сканворда из
> текстового словаря, пишу компоненту ну и собственно программу

Ты думаешь, это о чем-то говорит?

← →
Gydvin © (2006-01-31 11:58) [7]

короче есть шаблон кроссворда, с пятью строками под слова (а:=5);
мы в цикле предвигаемся по этим строкам ( while x<a do begin) и пытаемся по маске этой строки полученой из der(x) создать список возможных вариантов слов на эту строку, предварительно отвильтрованную по длине и убрав оттуда слова из предыдущих проходов. Из этого списка мы случайным образом выдергиваем одно слово и вставляем его в строку, если же список возможных слов пуст то делам шаг назад на предыдущую строку и ставим туда другое слово.

Тоесть получается алгоритм прямого перебора.

зы. Соответственно строки в шаблоне пересекаются и места пересечения отображаются на маске например.
есть 2 строки котрые пересекаются вот так

(2)
(1) 000000
0
0
0
0
И если мы первую строку заполним словом "поляна"
то маска второго слова будет "о????"

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

← →
Gero © (2006-01-31 12:07) [8]

> сам код я специально для сабжа собрал из разных функций

То, что ты собрал, нечитабельно.

← →
Gydvin © (2006-01-31 12:08) [9]

Коменты повыкидывать?

← →
Gero © (2006-01-31 12:19) [10]

> Gydvin © (31.01.06 12:08)

Дело не в комментариях, хотя их тоже должно быть в меру. Нормально назови все индентефикаторы, нормально фороми отступы, названия идетефикаторов пиши так, КакСоветуетБорланд. Все это помести не в button1click, а в процедуру с параметрами. Продукай, возможно что-то имеет смысл вынести в отдельные йнкции.
При беглом взгляде видно, что использован goto для органицации цикла — выбрось в топку.
Randomize тоже ни к чему, его достаточно вызывать один раз в секции initialization.

← →
Gero © (2006-01-31 12:21) [11]

> Gydvin © (31.01.06 12:08)

Кстати, неясно зачем тебе вобще Randomize, у тебя и Random"а-то нету.

Память, выделенную под объекты, нужно освобождать.

← →
Gydvin © (2006-01-31 12:26) [12]

Corry

s:=list2.Strings[(list2.Count)];

то

s:=list2.Strings[random(list2.Count)];

Память, выделенную под объекты, нужно освобождать.

setlength(r,0); list1.free; list.free; list2.free; end;

;))

← →
Gero © (2006-01-31 12:29) [13]

> setlength(r,0); list1.free; list.free; list2.free;
> end;

В первом посте такого нет. Но в любом случае, это неправильно.
Если хочешь двигаться дальше, сделай то, что я сказал в [10] и [11].

← →
Gydvin © (2006-01-31 13:00) [14]

to [10]
Для организации цикла использован while, goto же использован для отката на одну строку назад и недопуска записи левого слова в использованные.

на даном этапе меня другое напрягает, нет ли возможности r[x]:=r[x]+s+#13#10; заменить на что небуть более быстрое и независимое от наполняемости (ну чтоб скорость выполнения цикла не падала, по мере его заполнения)

Randomize тоже ни к чему, его достаточно вызывать один раз в секции initialization.

И что потом в цикле использования только рандом будет достаточно?

← →
Gero © (2006-01-31 13:03) [15]

> нет ли возможности r[x]:=r[x]+s+#13#10; заменить на что
> небуть более быстрое

А почему ты решил, что эта конструкция медленно выполняется?
> ну чтоб скорость выполнения цикла не падала, по мере его
> заполнения

А кто тебе сказал что она падает?

> И что потом в цикле использования только рандом будет достаточно?

Да.

А почему ты решил, что эта конструкция медленно выполняется?
Потому что я тестил? где-то после 100 проходов, в каждом добавляя по 6 символов (4 символа+каретка) у нас r[x] образовывается 6000 символов и скорость выполнения цикла заметно падаете, как только при неудачной комбинации происходит его очищение скоростьопять возрастает :(, а проходов может быть и 200 и 300 и 1000

А почему ты решил, что это именно эта конструкция? Там, что, других конструкций нет?

Ой и правда не она.

Тады остается только эта?!!

list2.Text:=r[x]; ////здесь удаляем из списка ранее проверенные for y:=0 to list2.Count-1 do begin s1:=list2.Strings[y]; t:=list1.IndexOf(s1); if t>-1 then list1.Delete(t); end;

> list2.Text:=r[x];

Можешь в исходнике посмотреть что при этом происходит.

> t:=list1.IndexOf(s1);

И при этом.

Gero © (31.01.06 16:52) [19]

Да я уже понял, спасибо.

Вот это и называется ткнуть носом :))

ЗЫ. Слышал, да и видел, в уже готовых программах, что существуют другие алгоритмы пребора кроме прямого, может кто в курсе, как это реализовано.

Спрашивал у гугла, он мне сказал или плати деньги за исходный код или иди нафиг.

может кто в курсе, как это реализовано.
Тут я поторопился, лучше так

Может кто слышал о других методах перебора, кроме "прямого" и знает хтябы примерно в какую сторону копать, может ссылки есть или документашка.

Перебор Найти похожие ветки