隨著配備高保真傳感器的移動設備的普及以及無線網(wǎng)絡資費的迅速下降，空間眾包成為一種新型的問題解決框架，被用于將位置相關的任務（如路況報告，食品配送）分配給工人（配備智能設備并愿意完成任務的人）．本文研究空間眾包中最優(yōu)任務分配問題，關鍵在于設計出將每個任務分配給最合適的工人的任務分配策略，以使得完成的總?cè)蝿諗?shù)目最大化，而所有的工人可以在完成所分配的任務后，在預期最晚工作時間之前返回起點，找到全局最優(yōu)分配是一個棘手的問題，因為該問題不等于單個工人的最佳分配的簡單累加．本文注意到，僅有部分工人存在任務依賴，因此本文利用樹分解技術將工人分割成獨立的集合，并提出一種帶啟發(fā)式的深度優(yōu)先搜索算法，該算法可以快速地更新啟發(fā)函數(shù)界限，從而高效的對不可能成為最優(yōu)解分配方案盡早地剪枝，實驗表明，本文所提出的方法是非常有效的，可以很好地解決最優(yōu)任務分配問題．