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

Тема в разделе "Pascal and Delphi", создана пользователем VESPER, 12 ноя 2010.

Статус темы:
Закрыта.
  1. VESPER

    VESPER Гость

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

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

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

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

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

    nayke Well-Known Member

    Регистрация:
    4 авг 2010
    Сообщения:
    310
    Симпатии:
    0
    Если все прямоугольники одинаковые и накладывать их надо на прямоугольник то задача элементарная.. высота ресурса div высота прямоугольника(накладываемого).и также ширина получишь значение количества рядов.. тогда можно посчитать остатки или отрисовать смотрячто нужно.
    если нет то здадача напоминает задачу про сбор рюкзака.. либо попробовать перебор..
     
  3. flashkpi

    flashkpi Гость

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

    XTen Active Member

    Регистрация:
    18 сен 2010
    Сообщения:
    26
    Симпатии:
    0
    Пиши решу Дёшево
    ICQ: 410691984
     
  5. VESPER

    VESPER Гость

    nayke

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

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

    nayke Well-Known Member

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

    VESPER Гость

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

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

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

    nayke Well-Known Member

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

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

    VESPER Гость

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

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

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

    nayke Well-Known Member

    Регистрация:
    4 авг 2010
    Сообщения:
    310
    Симпатии:
    0
    А сам то код где?

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

    VESPER Гость

    Код (LotusScript):
    #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
    И продолжение...

    Код (LotusScript):
        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
    Есть ещё код рекурсии, если есть желание посмотреть его могу выложить)

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

    nayke Well-Known Member

    Регистрация:
    4 авг 2010
    Сообщения:
    310
    Симпатии:
    0
    Ты бы сначала отладил алгоритм на простых примерах а потом графику подставлял.. это разумней как мне кажется..
     
  13. VESPER

    VESPER Гость

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

    Код (Delphi):
    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;
     
  14. nayke

    nayke Well-Known Member

    Регистрация:
    4 авг 2010
    Сообщения:
    310
    Симпатии:
    0
    пример денег это совсем не то.. С деньгами все просто меняешь сначала большими потом когда сумма которую надо разменять меньше данного номинала меняется следующей по нооминалу купюрой.. у тебя с прямоугольниками задача намного сложнее..или условия курсовика поменялись?
     
  15. VESPER

    VESPER Гость

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

    nayke Well-Known Member

    Регистрация:
    4 авг 2010
    Сообщения:
    310
    Симпатии:
    0
    Утебя задача сложне.. т.е. например имея квадрат 3*3 клетки тебе надо отложить в нем 2 квадрата 2*2 клетки.. если подходить к ней с точки зрения размена денег, то площадь первого 9 площадь тех, которые необходимо откладывать 8 (4+4) соответственно их можно отложить. Но реально вырезав один квадрат 2*2 места для второго уже не будет. т.е. Необходимо еще отслеживать откуда откладываются и возвожно ли отложить вообще..
    Как мне видется задача решается рекурсивно.. в рекурсивную процедуру передается массив координат от которых могут откладываться прямоугольники массив прямоугольников оставшихся.. и счетчик площади.. в нутри процедуры перебираются оставшиеся прямоугольники для всех возможных координат и вызывается эта же процедура при этом необходимо отслеживать возможность отложения того или иного прямоугольника..алгоритм не оптимальный но это первое что приходит в голову.
     
Загрузка...
Похожие Темы - Задача двоичной упаковки
  1. Янчик
    Ответов:
    0
    Просмотров:
    477
  2. TrishaRay
    Ответов:
    1
    Просмотров:
    778
  3. elzim
    Ответов:
    0
    Просмотров:
    929
  4. ShaoKahn
    Ответов:
    0
    Просмотров:
    1.117
  5. eremin-sanek
    Ответов:
    3
    Просмотров:
    1.104
Статус темы:
Закрыта.

Поделиться этой страницей