Задача двоичной упаковки с применением генетического блочного алгоритм

[VESPER]

Это курсовой проект, который я взял "тыкнув пальцем в небо"))

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

Язык программирования Object Pascal(Delphi 7)

Т.к. общий стаж работы с данным языком не превышает 100 часов я ещё достаточно плохо разбираюсь в нём... Поэтому строго прошу не судить)) могу чего-то не понимать)) но несмотря на это пишите свои предложения)) буду учится))) и к сожаленью у меня ограничено время на выполнение курсового((( с программой надо разобратся до 1 декабря(((

P.S. прошу извенения за ошибки))
P.P.S. доброго времени суток всем^^

 

[nayke]

Если все прямоугольники одинаковые и накладывать их надо на прямоугольник то задача элементарная.. высота ресурса div высота прямоугольника(накладываемого).и также ширина получишь значение количества рядов.. тогда можно посчитать остатки или отрисовать смотрячто нужно.
если нет то здадача напоминает задачу про сбор рюкзака.. либо попробовать перебор..

 

[flashkpi]

Пишите подробнее на:
icq: 588002847
email: flash_1989@ukr.net

 

[XTen]

Пиши решу Дёшево
ICQ: 410691984

 

[VESPER]

nayke

В этом то и проблемма))) Все фигуры задаются пользователем)) Задача о рюкзаке похожа, но переделывать её под эту для меня не оч удобно))) и я забыл написать что всё это надо проиллюстрировать))) что-бы было видно как были размещенны фигуры по полотну и где осталось неиспользуемое пространство...

А вот насчёт перебора я не думал... можешь поподробней про это написать?))

 

[nayke]

Первое что приходит на ум - рекурсивный алгоритм. В цикле выбираешь начальный прямоугольник.. отрезаешь площадь от материала.. вызываешь эту же процедуру для остальных.. для каждого подсчитываешь остаток площади(он и будет критерием оптимальности). Вот только твоя проблема в том что тебе еще надо смотреть возможно ли из оставшегося прямоугольника вырезать нужные тебе по размеру.. если опыт небольшой и зная как тестируют курсовые можно сделать матрицу забитую 0-пусто 1 -отрезано и проверять возможность наложения прямоугольника. У тебя же в задаче необходимо оставить как можно меньше материала? ограничение на количество прямоугольников есть(например отложить как можно больше прямоугольников в материале..)?

 

[VESPER]

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

Да самая проблемма это сделать так что бы не было такого как наложение одной фигуры на другую))) ато печально получится))) резать из уже вырезанного)))

я вот понять не могу, у меня в задаче будет использоваться гельётинная резка или нет... Читая другие форумы наткнулся на проблемму резки... пишут про две разные... и какая из них нужна мне я так и не понял...

 

[nayke]

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

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

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

 

[VESPER]

Про вершины вроде бы как понял)

Порывшись в нете я нашёл решение данной задачи)) но понять его не могу... VB и C# мне как языки не известны))) если можете помочь с переводом кода буду благодарен)))

Или попробуйте обьяснить как мне в делфи нарисовать это всё))) я незнаю канвас прокатит или нет в этом деле))

 

[nayke]

Про вершины вроде бы как понял)

Порывшись в нете я нашёл решение данной задачи)) но понять его не могу... VB и C# мне как языки не известны))) если можете помочь с переводом кода буду благодарен)))

А сам то код где?

Или попробуйте обьяснить как мне в делфи нарисовать это всё))) я незнаю канвас прокатит или нет в этом деле))

Рисовать прямоугольники это как раз задача канваса смотри метод rectangle.. начальные координаты у тебя есть, параметры прямоугольника(длина, высота) для определения вторых тоже так что вперед..

 

[VESPER]

#Region "Exhaustive Search"

#Const DEBUG4 = True
#If DEBUG4 Then
Private exhaustive_num_nodes As Long
Private exhaustive_num_leaves As Long
Private exhaustive_num_improvements As Long
#End If

' Perform an exhaustive search.
Public Sub AlgExhaustive(ByVal bin_width As Integer, ByVal rects() As Rectangle)
' Run a quick search to get an upper bound.
AlgSortByHeight(bin_width, rects)

' Make an array to record covered positions.
Dim max_y As Integer = MaxY(rects)
Dim used(bin_width - 1, max_y - 1) As Boolean

' Warn the user.
If rects.Length > 7 Then
If MessageBox.Show("This could take a very long time." & vbCrLf & vbCrLf & _
"Do you want to continue?", _
"Continue?", _
MessageBoxButtons.YesNo, _
MessageBoxIcon.Question) = DialogResult.No _
Then
For i As Integer = 0 To rects.Length - 1
rects(i).X = bin_width
Next i
Exit Sub
End If
End If

' Copy the rectangles.
Dim best_rects() As Rectangle = DirectCast(rects.Clone(), Rectangle())
Dim best_max_y As Integer = max_y

' Start the search.
#If DEBUG4 Then
exhaustive_num_nodes = 0
exhaustive_num_leaves = 0
exhaustive_num_improvements = 0
#End If
FillExhaustive(best_rects, best_max_y, rects, 0, used)
#If DEBUG4 Then
Debug.WriteLine("Examined " & _
exhaustive_num_nodes & " nodes and " & _
exhaustive_num_leaves & " leaves with " & _
exhaustive_num_improvements & " improvements")
#End If

' Save the solution.
Array.Copy(best_rects, rects, rects.Length)
End Sub

И продолжение...

	Private Sub FillExhaustive(ByRef best_rects() As Rectangle, ByRef best_max_y As Integer, ByVal rects() As Rectangle, ByVal next_i As Integer, ByVal used(,) As Boolean)
#If DEBUG4 Then
exhaustive_num_nodes += 1
#End If
' See if we're at a leaf node.
If next_i >= rects.Length Then
#If DEBUG4 Then
exhaustive_num_leaves += 1
#End If
' We're at a leaf node. See if this solution is an improvement.
Dim max_y As Integer = MaxY(rects)
If best_max_y > max_y Then
#If DEBUG4 Then
exhaustive_num_improvements += 1
#End If
best_max_y = max_y
best_rects = DirectCast(rects.Clone(), Rectangle())
End If
Else
Dim rect As Rectangle = rects(next_i)
For y As Integer = 0 To used.GetUpperBound(1) - rect.Height + 1
For x As Integer = 0 To used.GetUpperBound(0) - rect.Width + 1
' See if we can put the rectangle here.
Dim can_fit As Boolean = True
For i As Integer = 0 To rect.Width - 1
For j As Integer = 0 To rect.Height - 1
If used(x + i, y + j) Then
can_fit = False
Exit For
End If
Next j
If Not can_fit Then Exit For
Next i

' Give it a try.
If can_fit Then
' Put the rectangle here.
rects(next_i).X = x
rects(next_i).Y = y
For i As Integer = 0 To rect.Width - 1
For j As Integer = 0 To rect.Height - 1
used(x + i, y + j) = True
Next j
Next i

' Recurse.
FillExhaustive(best_rects, best_max_y, rects, next_i + 1, used)

' Un-put the rectangle here.
For i As Integer = 0 To rect.Width - 1
For j As Integer = 0 To rect.Height - 1
used(x + i, y + j) = False
Next j
Next i
End If
Next x
Next y
End If
End Sub

#End Region ' Exhaustive Search

Есть ещё код рекурсии, если есть желание посмотреть его могу выложить)

Попробую сегодня в канвасе поиграть) если что-нить получится выложу код)

 

[nayke]

Ты бы сначала отладил алгоритм на простых примерах а потом графику подставлял.. это разумней как мне кажется..

 

[VESPER]

Я на примере денег сделать смог алгоритм... т.е. даётся некая сумма денег, есть купюры определённого наминала... и надо меньшим количеством купюр разменять ту сумму которая нам данна... но вот что то с канвасом я ещё не подружился... и не понимаю как всё это реализовать))

const
nyu : array[1..8] of integer =
(5000, 1000, 500, 100, 50, 10, 5, 1);
var
X : integer;
i, Ni : integer;
s : string;
begin
X := StrToInt(Edi1.Text);
s := '';

i := 1;
while X>0 do begin
Ni := X div myu[i];
if Ni>0 then
s := s + ' '+IntToStr(Ni)+'*'+
IntToStr(nyu[i])+' ';
X := X - Ni * nyu[i];
i := i + 1;
end;
Edt2.Text := s;
end;

 

[nayke]

пример денег это совсем не то.. С деньгами все просто меняешь сначала большими потом когда сумма которую надо разменять меньше данного номинала меняется следующей по нооминалу купюрой.. у тебя с прямоугольниками задача намного сложнее..или условия курсовика поменялись?

 

[VESPER]

Все осталось на месте, я думал можно это как нибудь прилепить к моей проге)

 

[nayke]

Все осталось на месте, я думал можно это как нибудь прилепить к моей проге)

Утебя задача сложне.. т.е. например имея квадрат 3*3 клетки тебе надо отложить в нем 2 квадрата 2*2 клетки.. если подходить к ней с точки зрения размена денег, то площадь первого 9 площадь тех, которые необходимо откладывать 8 (4+4) соответственно их можно отложить. Но реально вырезав один квадрат 2*2 места для второго уже не будет. т.е. Необходимо еще отслеживать откуда откладываются и возвожно ли отложить вообще..
Как мне видется задача решается рекурсивно.. в рекурсивную процедуру передается массив координат от которых могут откладываться прямоугольники массив прямоугольников оставшихся.. и счетчик площади.. в нутри процедуры перебираются оставшиеся прямоугольники для всех возможных координат и вызывается эта же процедура при этом необходимо отслеживать возможность отложения того или иного прямоугольника..алгоритм не оптимальный но это первое что приходит в голову.