• B правой части каждого сообщения есть стрелки и . Не стесняйтесь оценивать ответы. Чтобы автору вопроса закрыть свой тикет, надо выбрать лучший ответ. Просто нажмите значок в правой части сообщения.

  • Познакомьтесь с пентестом веб-приложений на практике в нашем новом бесплатном курсе

    «Анализ защищенности веб-приложений»

    🔥 Записаться бесплатно!

  • CTF с учебными материалами Codeby Games

    Обучение кибербезопасности в игровой форме. Более 200 заданий по Active Directory, OSINT, PWN, Веб, Стеганографии, Реверс-инжинирингу, Форензике и Криптографии. Школа CTF с бесплатными курсами по всем категориям.

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

  • Автор темы VESPER
  • Дата начала
Статус
Закрыто для дальнейших ответов.
V

VESPER

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

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

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

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

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

nayke

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

VESPER

nayke

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

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

nayke

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

VESPER

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

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

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

nayke

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

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

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

VESPER

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

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

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

nayke

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

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

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

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

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

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

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

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

nayke

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

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;
 
N

nayke

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

VESPER

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

nayke

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

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

Обучение наступательной кибербезопасности в игровой форме. Начать игру!