Hasilkan persamaan dengan nilai hasil yang paling mendekati yang diminta, memiliki masalah kecepatan

Anda dapat membangun semua kemungkinan pohon ekspresi dengan angka-angka yang diberikan dan mengevaluasinya. Anda tidak perlu menyimpan semuanya di memori, cukup cetak ketika nomor target ditemukan:

Pertama kita membutuhkan kelas untuk menampung ekspresi. Lebih baik mendesainnya agar tidak dapat diubah, sehingga nilainya dapat dihitung sebelumnya. Sesuatu seperti ini:

class Expr:
    '''An Expr can be built with two different calls:
           -Expr(number) to build a literal expression
           -Expr(a, op, b) to build a complex expression. 
            There a and b will be of type Expr,
            and op will be one of ('+','-', '*', '/').
    '''
    def __init__(self, *args):
        if len(args) == 1:
            self.left = self.right = self.op = None
            self.value = args[0]
        else:
            self.left = args[0]
            self.right = args[2]
            self.op = args[1]
            if self.op == '+':
                self.value = self.left.value + self.right.value
            elif self.op == '-':
                self.value = self.left.value - self.right.value
            elif self.op == '*':
                self.value = self.left.value * self.right.value
            elif self.op == '/':
                self.value = self.left.value // self.right.value

    def __str__(self):
        '''It can be done smarter not to print redundant parentheses,
           but that is out of the scope of this problem.
        '''
        if self.op:
            return "({0}{1}{2})".format(self.left, self.op, self.right)
        else:
            return "{0}".format(self.value)

Sekarang kita dapat menulis fungsi rekursif yang membangun semua kemungkinan pohon ekspresi dengan serangkaian ekspresi tertentu, dan mencetak ekspresi yang sama dengan nilai target kita. Kami akan menggunakan modul itertools, itu selalu menyenangkan.

Kita bisa menggunakan itertools.combinations() atau itertools.permutations(), yang membedakan adalah urutannya. Beberapa operasi kita bersifat komutatif dan ada pula yang tidak, jadi kita dapat menggunakan permutations() dan berasumsi kita akan mendapatkan banyak solusi yang sangat mirip. Atau kita dapat menggunakan combinations() dan menyusun ulang nilainya secara manual ketika operasinya tidak bersifat komutatif.

import itertools
OPS = ('+', '-', '*', '/')
def SearchTrees(current, target):
    ''' current is the current set of expressions.
        target is the target number.
    '''
    for a,b in itertools.combinations(current, 2):
        current.remove(a)
        current.remove(b)
        for o in OPS:
            # This checks whether this operation is commutative
            if o == '-' or o == '/':
                conmut = ((a,b), (b,a))
            else:
                conmut = ((a,b),)

            for aa, bb in conmut:
                # You do not specify what to do with the division.
                # I'm assuming that only integer divisions are allowed.
                if o == '/' and (bb.value == 0 or aa.value % bb.value != 0):
                    continue
                e = Expr(aa, o, bb)
                # If a solution is found, print it
                if e.value == target:
                    print(e.value, '=', e)
                current.add(e)
                # Recursive call!
                SearchTrees(current, target)
                # Do not forget to leave the set as it were before
                current.remove(e)
        # Ditto
        current.add(b)
        current.add(a)

Dan kemudian panggilan utama:

NUMBERS = [4, 8, 6, 2, 15, 50]
TARGET = 590

initial = set(map(Expr, NUMBERS))
SearchTrees(initial, TARGET)

Dan selesai! Dengan data ini saya mendapatkan 719 solusi berbeda hanya dalam waktu 21 detik! Tentu saja banyak di antaranya yang merupakan variasi sepele dari ekspresi yang sama.

Semua kombinasi untuk enam angka, empat operasi dan tanda kurung maksimal 5 * 9! setidaknya. Jadi menurut saya Anda harus menggunakan beberapa algoritma AI. Menggunakan pemrograman genetik atau optimasi tampaknya merupakan jalan yang harus diikuti.

Dalam buku Pemrograman Kecerdasan Kolektif pada bab 11 Dengan Mengembangkan Kecerdasan Anda akan menemukan apa yang Anda inginkan dan banyak lagi. Bab tersebut menjelaskan cara menemukan fungsi matematika yang menggabungkan operasi dan angka (sesuai keinginan) untuk mencocokkan suatu hasil. Anda akan terkejut betapa mudahnya tugas tersebut.

PD: Contohnya ditulis menggunakan Python.

Saya akan mencoba menggunakan AST setidaknya itu akan
membuat bagian pembuatan ekspresi Anda lebih mudah
(tidak perlu dipusingkan dengan tanda kurung).

http://en.wikipedia.org/wiki/Abstract_syntax_tree

1) Hasilkan beberapa pohon dengan N node
(N = jumlah angka yang Anda miliki).
Saya sudah membaca sebelumnya berapa banyak angka yang Anda
miliki, ukurannya akan semakin besar seiring bertambahnya N.
Yang saya maksud dengan serius adalah lebih dari sekadar polinomial.

2) Sekarang mulailah mengubah operasi
pada node non-daun dan terus evaluasi
hasilnya.

Namun hal ini lagi-lagi merupakan kemunduran dan terlalu banyak derajat kebebasan.
Ini adalah tugas komputasi rumit yang Anda ajukan. Saya percaya jika Anda
mengajukan pertanyaan seperti yang Anda lakukan: "mari kita hasilkan angka K pada output
sedemikian rupa sehingga |K-V| minimal" (di sini V adalah hasil yang diinginkan yang telah ditentukan sebelumnya,
yaitu 590 dalam contoh Anda) , maka saya kira masalah ini bahkan NP-lengkap.

Seseorang tolong koreksi saya jika intuisi saya berbohong kepada saya.

Jadi saya pikir bahkan generasi semua kemungkinan AST (dengan asumsi hanya 1 operasi
yang diperbolehkan) apakah NP selesai karena hitungannya tidak polinomial. Belum lagi
lebih dari 1 operasi diperbolehkan di sini dan belum lagi persyaratan perbedaan minimal
(antara hasil dan hasil yang diinginkan).

24 permainan adalah 4 angka untuk ditargetkan 24, permainan Anda adalah 6 angka untuk ditargetkan x (0 ‹ x ‹ 1000).

Itu sangat mirip.

Ini solusi cepatnya, dapatkan semua hasil dan cetak satu saja di rMBP saya sekitar 1-3s, menurut saya satu solusi cetak oke di game ini :), nanti saya jelaskan:

def mrange(mask):
    #twice faster from Evgeny Kluev
    x = 0
    while x != mask:
        x = (x - mask) & mask
        yield x 

def f( i ) :
    global s
    if s[i] :
        #get cached group
        return s[i]
    for x in mrange(i & (i - 1)) :
        #when x & i == x
        #x is a child group in group i
        #i-x is also a child group in group i
        fk = fork( f(x), f(i-x) )
        s[i] = merge( s[i], fk )
    return s[i] 

def merge( s1, s2 ) :
    if not s1 :
        return s2
    if not s2 :
        return s1
    for i in s2 :
        #print just one way quickly
        s1[i] = s2[i]
        #combine all ways, slowly
        # if i in s1 :
        #   s1[i].update(s2[i])
        # else :
        #   s1[i] = s2[i]
    return s1   

def fork( s1, s2 ) :
    d = {}
    #fork s1 s2
    for i in s1 :
        for j in s2 :
            if not i + j in d :
                d[i + j] = getExp( s1[i], s2[j], "+" )
            if not i - j in d :
                d[i - j] = getExp( s1[i], s2[j], "-" )
            if not j - i in d :
                d[j - i] = getExp( s2[j], s1[i], "-" )
            if not i * j in d :
                d[i * j] = getExp( s1[i], s2[j], "*" )
            if j != 0 and not i / j in d :
                d[i / j] = getExp( s1[i], s2[j], "/" )
            if i != 0 and not j / i in d :
                d[j / i] = getExp( s2[j], s1[i], "/" )
    return d    

def getExp( s1, s2, op ) :
    exp = {}
    for i in s1 :
        for j in s2 :
            exp['('+i+op+j+')'] = 1
            #just print one way
            break
        #just print one way
        break
    return exp  

def check( s ) :
    num = 0
    for i in xrange(target,0,-1):
        if i in s :
            if i == target :
                print numbers, target, "\nFind ", len(s[i]), 'ways'
                for exp in s[i]:
                    print exp, ' = ', i
            else :
                print numbers, target, "\nFind nearest ", i, 'in', len(s[i]), 'ways'
                for exp in s[i]:
                    print exp, ' = ', i
            break
    print '\n'  

def game( numbers, target ) :
    global s
    s = [None]*(2**len(numbers))
    for i in xrange(0,len(numbers)) :
        numbers[i] = float(numbers[i])
    n = len(numbers)
    for i in xrange(0,n) :
        s[2**i] = { numbers[i]: {str(numbers[i]):1} }   

    for i in xrange(1,2**n) :
        #we will get the f(numbers) in s[2**n-1]
        s[i] = f(i) 

    check(s[2**n-1])    



numbers = [4, 8, 6, 2, 2, 5]
s = [None]*(2**len(numbers))    

target = 590
game( numbers, target ) 

numbers = [1,2,3,4,5,6]
target = 590
game( numbers, target )

Asumsikan A adalah daftar 6 angka Anda.

Kita definisikan f(A) adalah semua hasil yang dapat dihitung dengan semua A angka, jika kita mencari f(A), kita akan menemukan apakah target ada di dalamnya dan mendapatkan jawaban atau jawaban terdekat.

Kita dapat membagi A menjadi dua kelompok anak nyata: A1 dan A-A1 (A1 tidak kosong dan tidak sama dengan A) , yang memotong soal dari f(A) menjadi f(A1) dan f(A-A1). Karena kita tahu f(A) = Union( a+b, a-b, b-a, a*b, a/b(b!=0), b/a(a!=0) ), yang mana a di A, b di A-A1.

Kami menggunakan fork f(A) = Union( fork(A1,A-A1) ) singkatan dari proses tersebut. Kita dapat menghapus semua nilai duplikat di fork(), sehingga kita dapat memotong rentangnya dan membuat program lebih cepat.

Jadi, jika A = [1,2,3,4,5,6], maka f(A) = fork( f([1]),f([2,3,4,5,6]) ) U ... U fork( f([1,2,3]), f([4,5,6]) ) U ... U adalah singkatan dari Union.

Kita akan melihat f([2,3,4,5,6]) = garpu( f([2,3]), f([4,5,6]) ) U ... , f([3, 4,5,6]) = fork( f([3]), f([4,5,6]) ) U ..., f([4,5,6]) digunakan di keduanya.

Jadi jika kita bisa cache setiap f([...]) maka programnya bisa lebih cepat.

Kita bisa mendapatkan 2^len(A) - 2 (A1,A-A1) di A. Kita bisa menggunakan biner sebagai singkatannya.

Misal: A = [1,2,3,4,5,6], A1 = [1,2,3], maka biner 000111(7) adalah singkatan dari A1. A2 = [1,3,5], biner 010101(21) adalah singkatan dari A2. A3 = [1], maka biner 000001(1) adalah singkatan dari A3...

Jadi kita mendapatkan cara untuk semua grup di A, kita dapat menyimpannya dalam cache dan membuat semua proses lebih cepat!

1. Algoritma yang sepenuhnya online dan cepat

Idenya adalah untuk mencari bukan ekspresi tunggal untuk nilai target, namun untuk sebuah persamaan dimana nilai target dimasukkan dalam satu bagian persamaan dan kedua bagian memiliki jumlah operasi yang hampir sama (2 dan 3). Karena setiap bagian persamaan relatif kecil, tidak memerlukan banyak waktu untuk menghasilkan semua kemungkinan ekspresi untuk nilai masukan tertentu. Setelah kedua bagian persamaan dihasilkan, Anda dapat memindai sepasang larik terurut yang berisi nilai ekspresi ini dan menemukan sepasang nilai yang sama (atau setidaknya paling cocok) di dalamnya. Setelah dua nilai yang cocok ditemukan, kita bisa mendapatkan ekspresi yang sesuai dan menggabungkannya menjadi satu ekspresi (dengan kata lain, selesaikan persamaannya).

Untuk menggabungkan dua pohon ekspresi bersama-sama kita dapat turun dari akar satu pohon ke daun "target", untuk setiap simpul di jalur ini, balikkan operasi yang sesuai ('*' to '/', '/' to '*' or '/', '+' to '-', '-' to '+' or '-'), dan pindahkan simpul akar "terbalik" ke pohon lain (juga sebagai simpul akar).

Algoritme ini lebih cepat dan mudah diimplementasikan ketika semua operasi dapat dibalik. Jadi yang terbaik adalah menggunakan pembagian floating point (seperti dalam implementasi saya) atau dengan pembagian rasional. Memotong pembagian bilangan bulat adalah kasus yang paling sulit karena menghasilkan hasil yang sama untuk input yang berbeda (42/25=1 dan 25/25 juga 1). Dengan pembagian bilangan bulat nol-sisa, algoritma ini memberikan hasil hampir seketika ketika hasil pasti tersedia, namun memerlukan beberapa modifikasi agar berfungsi dengan benar ketika hasil perkiraan diperlukan.

Lihat implementasi di Ideone.

2. Pendekatan yang lebih cepat dengan pra-pemrosesan offline

Seperti yang diperhatikan oleh @WolframH, tidak banyak kemungkinan kombinasi angka masukan. Hanya 3*3*(₄^9+4-1) = 4455 jika pengulangan memungkinkan. Atau 3*3*(₄⁹) = 1134 tanpa duplikat. Hal ini memungkinkan kita melakukan pra-pemrosesan semua kemungkinan masukan secara offline, menyimpan hasil dalam bentuk ringkas, dan ketika hasil tertentu diperlukan, dengan cepat membongkar salah satu nilai yang telah diproses sebelumnya.

Program pra-pemrosesan harus mengambil larik 6 angka dan menghasilkan nilai untuk semua ekspresi yang mungkin. Kemudian ia harus mengeluarkan nilai di luar rentang dan menemukan hasil terdekat untuk semua kasus yang tidak memiliki kecocokan persis. Semua ini dapat dilakukan dengan algoritma yang diusulkan oleh @Tim. Kodenya memerlukan sedikit modifikasi untuk melakukannya. Ini juga merupakan alternatif tercepat (belum). Karena pra-pemrosesan sedang offline, kita dapat menggunakan sesuatu yang lebih baik daripada interpretasi Python. Salah satu alternatifnya adalah PyPy, alternatif lainnya adalah menggunakan bahasa yang ditafsirkan dengan cepat. Pra-pemrosesan semua masukan yang mungkin tidak akan memakan waktu lebih dari beberapa menit.

Berbicara tentang memori yang diperlukan untuk menyimpan semua nilai yang telah diproses sebelumnya, satu-satunya masalah adalah ekspresi yang dihasilkan. Jika disimpan dalam bentuk string akan memakan waktu hingga 4455*999*30 byte atau 120Mb. Tapi setiap ekspresi bisa dikompresi. Ini dapat direpresentasikan dalam notasi postfix seperti ini: arg1 arg2 + arg3 arg4 + *. Untuk menyimpan ini kita memerlukan 10 bit untuk menyimpan semua permutasi argumen, 10 bit untuk menyimpan 5 operasi, dan 8 bit untuk menentukan bagaimana argumen dan operasi disisipkan (6 argumen + 5 operasi - 3 posisi yang telah ditentukan sebelumnya: dua yang pertama selalu merupakan argumen , yang terakhir selalu beroperasi). 28 bit per pohon atau 4 byte, artinya hanya 20Mb untuk seluruh kumpulan data dengan duplikat atau 5Mb tanpa duplikat.

3. Lambat sepenuhnya algoritma online

Ada beberapa cara untuk mempercepat algoritma di OP:

1. Peningkatan kecepatan terbesar dapat dicapai jika kita menghindari mencoba setiap operasi komutatif dua kali dan membuat pohon rekursi tidak terlalu bercabang.
2. Beberapa optimasi dimungkinkan dengan menghapus semua cabang yang hasil operasi pembagiannya nol.
3. Penghafalan (pemrograman dinamis) tidak dapat memberikan peningkatan kecepatan yang signifikan di sini, namun mungkin berguna.

Setelah menyempurnakan pendekatan OP dengan ide-ide berikut, percepatan sekitar 30x dapat dicapai:

from itertools import combinations

numbers = [4, 8, 6, 2, 15, 50]
target = best_value = 590
best_item = None
subsets = {}


def get_best(value, item):
    global best_value, target, best_item

    if value >= 0 and abs(target - value) < best_value:
        best_value = abs(target - value)
        best_item = item

    return value, item


def compare_one(value, op, left, right):
    item = ('(' + left + op + right + ')')
    return get_best(value, item)


def apply_one(left, right):
    yield compare_one(left[0] + right[0], '+', left[1], right[1])
    yield compare_one(left[0] * right[0], '*', left[1], right[1])
    yield compare_one(left[0] - right[0], '-', left[1], right[1])
    yield compare_one(right[0] - left[0], '-', right[1], left[1])

    if right[0] != 0 and left[0] >= right[0]:
        yield compare_one(left[0] / right[0], '/', left[1], right[1])

    if left[0] != 0 and right[0] >= left[0]:
        yield compare_one(right[0] / left[0], '/', right[1], left[1])


def memorize(seq):
    fs = frozenset(seq)

    if fs in subsets:
        for x in subsets[fs].items():
            yield x
    else:
        subsets[fs] = {}
        for value, item in try_all(seq):
            subsets[fs][value] = item
            yield value, item


def apply_all(left, right):
    for l in memorize(left):
        for r in memorize(right):
            for x in apply_one(l, r):
                yield x;


def try_all(seq):
    if len(seq) == 1:
        yield get_best(numbers[seq[0]], str(numbers[seq[0]]))

    for length in range(1, len(seq)):
        for x in combinations(seq[1:], length):
            for value, item in apply_all(list(x), list(set(seq) - set(x))):
                yield value, item


for x, y in try_all([0, 1, 2, 3, 4, 5]): pass

print best_item

Peningkatan kecepatan lebih lanjut dapat dilakukan jika Anda menambahkan beberapa batasan pada masalah:

1. Jika pembagian bilangan bulat hanya dapat dilakukan jika sisanya nol.
2. Jika semua hasil antara tidak negatif dan/atau di bawah 1000.

Yah, aku tidak akan menyerah. Mengikuti semua jawaban atas pertanyaan Anda, saya membuat algoritma lain. Algoritma ini memberikan solusi dengan waktu rata-rata 3 milidetik.

#! -*- coding: utf-8 -*-
import copy

numbers = [4, 8, 6, 2, 15, 50]
target = 590

operations  = {
    '+': lambda x, y: x + y, 
    '-': lambda x, y: x - y,
    '*': lambda x, y: x * y,
    '/': lambda x, y: y == 0 and 1e30 or x / y   # Handle zero division
}

def chain_op(target, numbers, result=None, expression=""):
    if len(numbers) == 0:
        return (expression, result)
    else:
        for choosen_number in numbers:
            remaining_numbers = copy.copy(numbers)
            remaining_numbers.remove(choosen_number)
            if result is None:
                return chain_op(target, remaining_numbers, choosen_number, str(choosen_number))
            else:
                incomming_results = []
                for key, op in operations.items():
                    new_result = op(result, choosen_number)
                    new_expression = "%s%s%d" % (expression, key, choosen_number)
                    incomming_results.append(chain_op(target, remaining_numbers, new_result, new_expression))
                diff = 1e30
                selected = None
                for exp_result in incomming_results:
                    exp, res = exp_result
                    if abs(res - target) < diff:
                        diff = abs(res - target)
                        selected = exp_result
                    if diff == 0:
                        break
                return selected

if __name__ == '__main__':
    print chain_op(target, numbers)

Kesalahan: Algoritme ini tidak menyertakan solusi yang mengandung tanda kurung. Selalu tepat sasaran atau hasil yang paling mendekati, salahku. Masih cukup cepat. Itu dapat diadaptasi untuk mendukung tanda kurung tanpa banyak usaha.

Sebenarnya ada dua hal yang dapat Anda lakukan untuk mempercepat waktu menjadi milidetik.

Anda mencoba mencari solusi untuk kuis yang diberikan, dengan menghasilkan angka dan nomor target. Sebagai gantinya, Anda dapat menghasilkan solusi dan menghapus operasinya saja. Anda dapat membuat sesuatu yang cerdas yang akan menghasilkan beberapa kuis dan memilih salah satu yang paling menarik, namun dalam kasus ini Anda kehilangan opsi sedekat mungkin.

Cara lain yang bisa dilakukan adalah pra-perhitungan. Selesaikan 100 kuis, gunakan kuis tersebut sebagai bawaan aplikasi Anda, dan buat kuis baru dengan cepat, usahakan agar tumpukan kuis Anda tetap di 100, juga coba berikan hanya kuis baru kepada pengguna. Saya mengalami masalah yang sama di permainan Alkitab saya , dan saya menggunakan metode ini untuk mempercepatnya. Daripada 10 detik untuk mengajukan pertanyaan, saya memerlukan waktu milidetik karena saya membuat pertanyaan baru di latar belakang dan selalu menjaga tumpukan saya hingga 100.

Bagaimana dengan pemrograman Dinamis, karena Anda memerlukan hasil yang sama untuk menghitung opsi lain?